




"""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  _snake_case				(							A__							,						A__							,						unittest.TestCase       ):

				'''simple docstring'''




				UpperCamelCase__		     =StableDiffusionXLPipeline
				UpperCamelCase__		     =TEXT_TO_IMAGE_PARAMS
				UpperCamelCase__		     =TEXT_TO_IMAGE_BATCH_PARAMS
				UpperCamelCase__		     =TEXT_TO_IMAGE_IMAGE_PARAMS
				UpperCamelCase__		     =TEXT_TO_IMAGE_IMAGE_PARAMS





				def 				snake_case_ (							self      :  Tuple     ):
								torch.manual_seed(0     )
								UpperCAmelCase_					:Dict      			=      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=snake_case					,							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_					:Optional[int]      			=      EulerDiscreteScheduler(
								    beta_start=0.00_085					,							beta_end=0.012					,							steps_offset=1					,							beta_schedule='''scaled_linear'''					,							timestep_spacing='''leading'''					,							)
								torch.manual_seed(0     )
								UpperCAmelCase_					:Union[str, Any]      			=      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=128					,							)
								torch.manual_seed(0     )
								UpperCAmelCase_					:Optional[Any]      			=      CLIPTextConfig(
								    bos_token_id=0					,							eos_token_id=2					,							hidden_size=32					,							intermediate_size=37					,							layer_norm_eps=1e-05					,							num_attention_heads=4					,							num_hidden_layers=5					,							pad_token_id=1					,							vocab_size=1_000					,							hidden_act='''gelu'''					,							projection_dim=32					,							)
								UpperCAmelCase_					:int      			=      CLIPTextModel(snake_case     )
								UpperCAmelCase_					:Dict      			=      CLIPTokenizer.from_pretrained('''hf-internal-testing/tiny-random-clip'''					,							local_files_only=snake_case     )

								UpperCAmelCase_					:int      			=      CLIPTextModelWithProjection(snake_case     )
								UpperCAmelCase_					:Union[str, Any]      			=      CLIPTokenizer.from_pretrained('''hf-internal-testing/tiny-random-clip'''					,							local_files_only=snake_case     )

								UpperCAmelCase_					:Optional[int]      			=      {
								    '''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 				snake_case_ (							self      :  Union[str, Any]					,							snake_case      :  Tuple					,							snake_case      :  int=0     ):
								if str(snake_case     ).startswith('''mps'''     ):
												UpperCAmelCase_					:Any      			=      torch.manual_seed(snake_case     )
								else:
												UpperCAmelCase_					:List[str]      			=      torch.Generator(device=snake_case     ).manual_seed(snake_case     )
								UpperCAmelCase_					:Any      			=      {
								    '''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 				snake_case_ (							self      :  List[str]     ):
								UpperCAmelCase_					:Optional[int]      			=      '''cpu'''  # ensure determinism for the device-dependent torch.Generator
								UpperCAmelCase_					:List[str]      			=      self.get_dummy_components()
								UpperCAmelCase_					:Union[str, Any]      			=      StableDiffusionXLPipeline(**snake_case     )
								UpperCAmelCase_					:List[str]      			=      sd_pipe.to(snake_case     )
								sd_pipe.set_progress_bar_config(disable=snake_case     )

								UpperCAmelCase_					:str      			=      self.get_dummy_inputs(snake_case     )
								UpperCAmelCase_					:List[Any]      			=      sd_pipe(**snake_case     ).images
								UpperCAmelCase_					:Optional[int]      			=      image[0, -3:, -3:, -1]

								assert image.shape == (1, 64, 64, 3)
								UpperCAmelCase_					:Optional[int]      			=      np.array([0.5_873, 0.6_128, 0.4_797, 0.5_122, 0.5_674, 0.4_639, 0.5_227, 0.5_149, 0.4_747]     )

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





				def 				snake_case_ (							self      :  Tuple     ):
								UpperCAmelCase_					:Optional[Any]      			=      self.get_dummy_components()
								UpperCAmelCase_					:Tuple      			=      StableDiffusionXLPipeline(**snake_case     )
								UpperCAmelCase_					:str      			=      sd_pipe.to(snake_case     )
								UpperCAmelCase_					:List[str]      			=      sd_pipe.to(snake_case     )
								sd_pipe.set_progress_bar_config(disable=snake_case     )

								# forward without prompt embeds
								UpperCAmelCase_					:List[Any]      			=      self.get_dummy_inputs(snake_case     )
								UpperCAmelCase_					:Union[str, Any]      			=      3 * ['''this is a negative prompt''']
								UpperCAmelCase_					:List[str]      			=      negative_prompt
								UpperCAmelCase_					:str      			=      3 * [inputs['''prompt''']]

								UpperCAmelCase_					:Optional[Any]      			=      sd_pipe(**snake_case     )
								UpperCAmelCase_					:Optional[int]      			=      output.images[0, -3:, -3:, -1]

								# forward with prompt embeds
								UpperCAmelCase_					:Union[str, Any]      			=      self.get_dummy_inputs(snake_case     )
								UpperCAmelCase_					:List[Any]      			=      3 * ['''this is a negative prompt''']
								UpperCAmelCase_					:Optional[int]      			=      3 * [inputs.pop('''prompt'''     )]

								(
								    (
								    UpperCAmelCase_
								)			,(
								    UpperCAmelCase_
								)			,(
								    UpperCAmelCase_
								)			,(
								    UpperCAmelCase_
								)			,
								)					:List[str]      			=      sd_pipe.encode_prompt(snake_case					,							negative_prompt=snake_case     )

								UpperCAmelCase_					:Any      			=      sd_pipe(
								    **snake_case					,							prompt_embeds=snake_case					,							negative_prompt_embeds=snake_case					,							pooled_prompt_embeds=snake_case					,							negative_pooled_prompt_embeds=snake_case					,							)
								UpperCAmelCase_					:List[Any]      			=      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 				snake_case_ (							self      :  Union[str, Any]     ):
								super().test_attention_slicing_forward_pass(expected_max_diff=3e-3     )





				def 				snake_case_ (							self      :  Optional[Any]     ):
								super().test_inference_batch_single_identical(expected_max_diff=3e-3     )



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

				'''simple docstring'''




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





				def 				snake_case_ (							self      :  int					,							snake_case      :  Union[str, Any]					,							snake_case      :  List[Any]="cpu"					,							snake_case      :  str=torch.floataa					,							snake_case      :  List[str]=0     ):
								UpperCAmelCase_					:Union[str, Any]      			=      torch.Generator(device=snake_case     ).manual_seed(snake_case     )
								UpperCAmelCase_					:Optional[Any]      			=      np.random.RandomState(snake_case     ).standard_normal((1, 4, 64, 64)     )
								UpperCAmelCase_					:List[str]      			=      torch.from_numpy(snake_case     ).to(device=snake_case					,							dtype=snake_case     )
								UpperCAmelCase_					:Optional[int]      			=      {
								    '''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 				snake_case_ (							self      :  Dict     ):
								UpperCAmelCase_					:Any      			=      DiffusionPipeline.from_pretrained('''stabilityai/stable-diffusion-2-base'''     )
								pipe.to(snake_case     )
								pipe.set_progress_bar_config(disable=snake_case     )

								UpperCAmelCase_					:Optional[Any]      			=      self.get_inputs(snake_case     )
								UpperCAmelCase_					:List[Any]      			=      pipe(**snake_case     ).images
								UpperCAmelCase_					:List[str]      			=      image[0, -3:, -3:, -1].flatten()

								assert image.shape == (1, 512, 512, 3)
								UpperCAmelCase_					:Dict      			=      np.array([0.49_493, 0.47_896, 0.40_798, 0.54_214, 0.53_212, 0.48_202, 0.47_656, 0.46_329, 0.48_506]     )
								assert np.abs(image_slice - expected_slice     ).max() < 7e-3








"""simple docstring"""

# This Python program implements an optimal binary search tree (abbreviated BST)
# building dynamic programming algorithm that delivers O(n^2) performance.
#
# The goal of the optimal BST problem is to build a low-cost BST for a
# given set of nodes, each with its own key and frequency. The frequency
# of the node is defined as how many time the node is being searched.
# The search cost of binary search tree is given by this formula:
#
# cost(1, n) = sum{i = 1 to n}((depth(node_i) + 1) * node_i_freq)
#
# where n is number of nodes in the BST. The characteristic of low-cost
# BSTs is having a faster overall search time than other implementations.
# The reason for their fast search time is that the nodes with high
# frequencies will be placed near the root of the tree while the nodes
# with low frequencies will be placed near the leaves of the tree thus
# reducing search time in the most frequent instances.
import sys
from random import randint



class  _snake_case				:

				'''simple docstring'''




				def __init__(							self      :  str					,							snake_case      :  Optional[Any]					,							snake_case      :  str     ):
								UpperCAmelCase_					:Union[str, Any]      			=      key
								UpperCAmelCase_					:str      			=      freq





				def __str__(							self      :  Optional[Any]     ):
								return f'Node(key={self.key}, freq={self.freq})'



def 				a (						__snake_case     :				int,    __snake_case     :				Optional[int],    __snake_case     :				Tuple,    __snake_case     :				Any,    __snake_case     :				Dict,    __snake_case     :				List[str]  ):



				'''simple docstring'''





				if i > j or i < 0 or j > len(__snake_case  ) - 1:
								return

				UpperCAmelCase_					:List[str]      			=      root[i][j]
				if parent == -1:  # root does not have a parent
								print(f'{key[node]} is the root of the binary search tree.'  )
				elif is_left:
								print(f'{key[node]} is the left child of key {parent}.'  )
				else:
								print(f'{key[node]} is the right child of key {parent}.'  )

				print_binary_search_tree(__snake_case,    __snake_case,    __snake_case,    node - 1,    key[node],    __snake_case  )
				print_binary_search_tree(__snake_case,    __snake_case,    node + 1,    __snake_case,    key[node],    __snake_case  )



def 				a (						__snake_case     :				Optional[Any]  ):



				'''simple docstring'''





				nodes.sort(key=lambda __snake_case  : node.key  )

				UpperCAmelCase_					:List[str]      			=      len(__snake_case  )

				UpperCAmelCase_					:Any      			=      [nodes[i].key for i in range(__snake_case  )]
				UpperCAmelCase_					:int      			=      [nodes[i].freq for i in range(__snake_case  )]

				# This 2D array stores the overall tree cost (which's as minimized as possible);
				# for a single key, cost is equal to frequency of the key.
				UpperCAmelCase_					:Dict      			=      [[freqs[i] if i == j else 0 for j in range(__snake_case  )] for i in range(__snake_case  )]
				# sum[i][j] stores the sum of key frequencies between i and j inclusive in nodes
				# array
				UpperCAmelCase_					:Optional[Any]      			=      [[freqs[i] if i == j else 0 for j in range(__snake_case  )] for i in range(__snake_case  )]
				# stores tree roots that will be used later for constructing binary search tree
				UpperCAmelCase_					:int      			=      [[i if i == j else 0 for j in range(__snake_case  )] for i in range(__snake_case  )]

				for interval_length in range(2,    n + 1  ):
								for i in range(n - interval_length + 1  ):
												UpperCAmelCase_					:Union[str, Any]      			=      i + interval_length - 1

												UpperCAmelCase_					:Optional[int]      			=      sys.maxsize  # set the value to "infinity"
												UpperCAmelCase_					:List[Any]      			=      total[i][j - 1] + freqs[j]

												# Apply Knuth's optimization
												# Loop without optimization: for r in range(i, j + 1):
												for r in range(root[i][j - 1],    root[i + 1][j] + 1  ):  # r is a temporal root
																UpperCAmelCase_					:Any      			=      dp[i][r - 1] if r != i else 0  # optimal cost for left subtree
																UpperCAmelCase_					:Optional[int]      			=      dp[r + 1][j] if r != j else 0  # optimal cost for right subtree
																UpperCAmelCase_					:Union[str, Any]      			=      left + total[i][j] + right

																if dp[i][j] > cost:
																				UpperCAmelCase_					:Optional[Any]      			=      cost
																				UpperCAmelCase_					:Optional[int]      			=      r

				print('''Binary search tree nodes:'''  )
				for node in nodes:
								print(__snake_case  )

				print(f'\nThe cost of optimal BST for given tree nodes is {dp[0][n - 1]}.'  )
				print_binary_search_tree(__snake_case,    __snake_case,    0,    n - 1,    -1,    __snake_case  )



def 				a (						):



				'''simple docstring'''





				UpperCAmelCase_					:Union[str, Any]      			=      [Node(__snake_case,    randint(1,    50  )  ) for i in range(10,    0,    -1  )]
				find_optimal_binary_search_tree(__snake_case  )


if __name__ == "__main__":
						main()


