


'''simple docstring'''

from typing import List, Optional, Union

import torch

from ...models import UNetaDConditionModel, VQModel
from ...pipelines import DiffusionPipeline
from ...pipelines.pipeline_utils import ImagePipelineOutput
from ...schedulers import DDPMScheduler
from ...utils import (
    is_accelerate_available,
    is_accelerate_version,
    logging,
    randn_tensor,
    replace_example_docstring,
)


lowercase__				     =		logging.get_logger(__name__)  # pylint: disable=invalid-name

lowercase__				     =		"\n    Examples:\n        ```py\n        >>> import torch\n        >>> import numpy as np\n\n        >>> from diffusers import KandinskyV22PriorPipeline, KandinskyV22ControlnetPipeline\n        >>> from transformers import pipeline\n        >>> from diffusers.utils import load_image\n\n\n        >>> def make_hint(image, depth_estimator):\n        ...     image = depth_estimator(image)[\"depth\"]\n        ...     image = np.array(image)\n        ...     image = image[:, :, None]\n        ...     image = np.concatenate([image, image, image], axis=2)\n        ...     detected_map = torch.from_numpy(image).float() / 255.0\n        ...     hint = detected_map.permute(2, 0, 1)\n        ...     return hint\n\n\n        >>> depth_estimator = pipeline(\"depth-estimation\")\n\n        >>> pipe_prior = KandinskyV22PriorPipeline.from_pretrained(\n        ...     \"kandinsky-community/kandinsky-2-2-prior\", torch_dtype=torch.float16\n        ... )\n        >>> pipe_prior = pipe_prior.to(\"cuda\")\n\n        >>> pipe = KandinskyV22ControlnetPipeline.from_pretrained(\n        ...     \"kandinsky-community/kandinsky-2-2-controlnet-depth\", torch_dtype=torch.float16\n        ... )\n        >>> pipe = pipe.to(\"cuda\")\n\n\n        >>> img = load_image(\n        ...     \"https://huggingface.co/datasets/hf-internal-testing/diffusers-images/resolve/main\"\n        ...     \"/kandinsky/cat.png\"\n        ... ).resize((768, 768))\n\n        >>> hint = make_hint(img, depth_estimator).unsqueeze(0).half().to(\"cuda\")\n\n        >>> prompt = \"A robot, 4k photo\"\n        >>> negative_prior_prompt = \"lowres, text, error, cropped, worst quality, low quality, jpeg artifacts, ugly, duplicate, morbid, mutilated, out of frame, extra fingers, mutated hands, poorly drawn hands, poorly drawn face, mutation, deformed, blurry, dehydrated, bad anatomy, bad proportions, extra limbs, cloned face, disfigured, gross proportions, malformed limbs, missing arms, missing legs, extra arms, extra legs, fused fingers, too many fingers, long neck, username, watermark, signature\"\n\n        >>> generator = torch.Generator(device=\"cuda\").manual_seed(43)\n\n        >>> image_emb, zero_image_emb = pipe_prior(\n        ...     prompt=prompt, negative_prompt=negative_prior_prompt, generator=generator\n        ... ).to_tuple()\n\n        >>> images = pipe(\n        ...     image_embeds=image_emb,\n        ...     negative_image_embeds=zero_image_emb,\n        ...     hint=hint,\n        ...     num_inference_steps=50,\n        ...     generator=generator,\n        ...     height=768,\n        ...     width=768,\n        ... ).images\n\n        >>> images[0].save(\"robot_cat.png\")\n        ```\n"






def __UpperCamelCase   (			__lowerCamelCase		: Dict      ,  __lowerCamelCase		: List[Any]      ,  __lowerCamelCase		: List[Any]=8				)      ->     Optional[int]:







     '''simple docstring'''






     _a						=		height // scale_factor**2
     if height % scale_factor**2 != 0:
          new_height += 1
     _a						=		width // scale_factor**2
     if width % scale_factor**2 != 0:
          new_width += 1
     return new_height * scale_factor, new_width * scale_factor






class 						__SCREAMING_SNAKE_CASE					(      lowerCamelCase__ ):






     def __init__(			self     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							)       ->    Optional[int]:
          super().__init__()

          self.register_modules(
              unet=__UpperCamelCase     ,							scheduler=__UpperCamelCase     ,							movq=__UpperCamelCase     ,							)
          _a						=		2 ** (len(self.movq.config.block_out_channels		) - 1)






     def  a_					(			self     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase		)       ->    List[str]:
          if latents is None:
               _a						=		randn_tensor(__UpperCamelCase     ,							generator=__UpperCamelCase     ,							device=__UpperCamelCase     ,							dtype=__UpperCamelCase		)
          else:
               if latents.shape != shape:
                    raise ValueError(f"Unexpected latents shape, got {latents.shape}, expected {shape}"		)
               _a						=		latents.to(__UpperCamelCase		)

          _a						=		latents * scheduler.init_noise_sigma
          return latents






     def  a_					(			self     ,							__UpperCamelCase=0		)       ->    int:
          if is_accelerate_available():
               from accelerate import cpu_offload
          else:
               raise ImportError("Please install accelerate via `pip install accelerate`"		)

          _a						=		torch.device(f"cuda:{gpu_id}"		)

          _a						=		[
              self.unet,
              self.movq,
          ]
          for cpu_offloaded_model in models:
               if cpu_offloaded_model is not None:
                    cpu_offload(__UpperCamelCase     ,							__UpperCamelCase		)






     def  a_					(			self     ,							__UpperCamelCase=0		)       ->    Optional[int]:
          if is_accelerate_available() and is_accelerate_version(">="     ,							"0.17.0.dev0"		):
               from accelerate import cpu_offload_with_hook
          else:
               raise ImportError("`enable_model_cpu_offload` requires `accelerate v0.17.0` or higher."		)

          _a						=		torch.device(f"cuda:{gpu_id}"		)

          if self.device.type != "cpu":
               self.to("cpu"     ,							silence_dtype_warnings=__UpperCamelCase		)
               torch.cuda.empty_cache()  # otherwise we don't see the memory savings (but they probably exist)

          _a						=		None
          for cpu_offloaded_model in [self.unet, self.movq]:
               _a			,			_a						=		cpu_offload_with_hook(__UpperCamelCase     ,							__UpperCamelCase     ,							prev_module_hook=__UpperCamelCase		)

          # We'll offload the last model manually.
          _a						=		hook






     @property
     # Copied from diffusers.pipelines.stable_diffusion.pipeline_stable_diffusion.StableDiffusionPipeline._execution_device
     def  a_					(			self		)       ->    int:
          if not hasattr(self.unet     ,							"_hf_hook"		):
               return self.device
          for module in self.unet.modules():
               if (
                   hasattr(__UpperCamelCase     ,							"_hf_hook"		)
                   and hasattr(module._hf_hook     ,							"execution_device"		)
                   and module._hf_hook.execution_device is not None
               ):
                    return torch.device(module._hf_hook.execution_device		)
          return self.device






     @torch.no_grad()
     @replace_example_docstring(__UpperCamelCase		)
     def __call__(			self     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase = 512     ,							__UpperCamelCase = 512     ,							__UpperCamelCase = 100     ,							__UpperCamelCase = 4.0     ,							__UpperCamelCase = 1     ,							__UpperCamelCase = None     ,							__UpperCamelCase = None     ,							__UpperCamelCase = "pil"     ,							__UpperCamelCase = True     ,							)       ->    List[Any]:
          _a						=		self._execution_device

          _a						=		guidance_scale > 1.0

          if isinstance(__UpperCamelCase     ,							__UpperCamelCase		):
               _a						=		torch.cat(__UpperCamelCase     ,							dim=0		)
          if isinstance(__UpperCamelCase     ,							__UpperCamelCase		):
               _a						=		torch.cat(__UpperCamelCase     ,							dim=0		)
          if isinstance(__UpperCamelCase     ,							__UpperCamelCase		):
               _a						=		torch.cat(__UpperCamelCase     ,							dim=0		)

          _a						=		image_embeds.shape[0] * num_images_per_prompt

          if do_classifier_free_guidance:
               _a						=		image_embeds.repeat_interleave(__UpperCamelCase     ,							dim=0		)
               _a						=		negative_image_embeds.repeat_interleave(__UpperCamelCase     ,							dim=0		)
               _a						=		hint.repeat_interleave(__UpperCamelCase     ,							dim=0		)

          _a						=		torch.cat([negative_image_embeds, image_embeds]     ,							dim=0		).to(dtype=self.unet.dtype     ,							device=__UpperCamelCase		)
          _a						=		torch.cat([hint, hint]     ,							dim=0		).to(dtype=self.unet.dtype     ,							device=__UpperCamelCase		)
          self.scheduler.set_timesteps(__UpperCamelCase     ,							device=__UpperCamelCase		)
          _a						=		self.scheduler.timesteps

          _a						=		self.movq.config.latent_channels

          _a			,			_a						=		downscale_height_and_width(__UpperCamelCase     ,							__UpperCamelCase     ,							self.movq_scale_factor		)

          # create initial latent
          _a						=		self.prepare_latents(
              (batch_size, num_channels_latents, height, width)     ,							image_embeds.dtype     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							self.scheduler     ,							)

          for i, t in enumerate(self.progress_bar(__UpperCamelCase		)		):
               # expand the latents if we are doing classifier free guidance
               _a						=		torch.cat([latents] * 2		) if do_classifier_free_guidance else latents

               _a						=		{"image_embeds": image_embeds, "hint": hint}
               _a						=		self.unet(
                   sample=__UpperCamelCase     ,							timestep=__UpperCamelCase     ,							encoder_hidden_states=__UpperCamelCase     ,							added_cond_kwargs=__UpperCamelCase     ,							return_dict=__UpperCamelCase     ,							)[0]

               if do_classifier_free_guidance:
                    _a			,			_a						=		noise_pred.split(latents.shape[1]     ,							dim=1		)
                    _a			,			_a						=		noise_pred.chunk(2		)
                    _a			,			_a						=		variance_pred.chunk(2		)
                    _a						=		noise_pred_uncond + guidance_scale * (noise_pred_text - noise_pred_uncond)
                    _a						=		torch.cat([noise_pred, variance_pred_text]     ,							dim=1		)

               if not (
                   hasattr(self.scheduler.config     ,							"variance_type"		)
                   and self.scheduler.config.variance_type in ["learned", "learned_range"]
               ):
                    _a			,			_a						=		noise_pred.split(latents.shape[1]     ,							dim=1		)

               # compute the previous noisy sample x_t -> x_t-1
               _a						=		self.scheduler.step(
                   __UpperCamelCase     ,							__UpperCamelCase     ,							__UpperCamelCase     ,							generator=__UpperCamelCase     ,							)[0]
          # post-processing
          _a						=		self.movq.decode(__UpperCamelCase     ,							force_not_quantize=__UpperCamelCase		)["sample"]

          if output_type not in ["pt", "np", "pil"]:
               raise ValueError(f"Only the output types `pt`, `pil` and `np` are supported not output_type={output_type}"		)

          if output_type in ["np", "pil"]:
               _a						=		image * 0.5 + 0.5
               _a						=		image.clamp(0     ,							1		)
               _a						=		image.cpu().permute(0     ,							2     ,							3     ,							1		).float().numpy()

          if output_type == "pil":
               _a						=		self.numpy_to_pil(__UpperCamelCase		)

          if not return_dict:
               return (image,)

          return ImagePipelineOutput(images=__UpperCamelCase		)





'''simple docstring'''

lowercase__				     =		256
# Modulus to hash a string
lowercase__				     =		1_000_003






def __UpperCamelCase   (			__lowerCamelCase		: str      ,  __lowerCamelCase		: str				)      ->     bool:







     '''simple docstring'''






     _a						=		len(__lowerCamelCase				)
     _a						=		len(__lowerCamelCase				)
     if p_len > t_len:
          return False

     _a						=		0
     _a						=		0
     _a						=		1

     # Calculating the hash of pattern and substring of text
     for i in range(__lowerCamelCase				):
          _a						=		(ord(pattern[i]				) + p_hash * alphabet_size) % modulus
          _a						=		(ord(text[i]				) + text_hash * alphabet_size) % modulus
          if i == p_len - 1:
               continue
          _a						=		(modulus_power * alphabet_size) % modulus

     for i in range(0      ,  t_len - p_len + 1				):
          if text_hash == p_hash and text[i : i + p_len] == pattern:
               return True
          if i == t_len - p_len:
               continue
          # Calculate the https://en.wikipedia.org/wiki/Rolling_hash
          _a						=		(
              (text_hash - ord(text[i]				) * modulus_power) * alphabet_size
              + ord(text[i + p_len]				)
          ) % modulus
     return False






def __UpperCamelCase   (			)      ->     None:







     '''simple docstring'''






     _a						=		"abc1abc12"
     _a						=		"alskfjaldsabc1abc1abc12k23adsfabcabc"
     _a						=		"alskfjaldsk23adsfabcabc"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				) and not rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 2)
     _a						=		"ABABX"
     _a						=		"ABABZABABYABABX"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 3)
     _a						=		"AAAB"
     _a						=		"ABAAAAAB"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 4)
     _a						=		"abcdabcy"
     _a						=		"abcxabcdabxabcdabcdabcy"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)

     # Test 5)
     _a						=		"Lü"
     _a						=		"Lüsai"
     assert rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)
     _a						=		"Lue"
     assert not rabin_karp(__lowerCamelCase      ,  __lowerCamelCase				)
     print("Success."				)


if __name__ == "__main__":
   test_rabin_karp()

