






import collections
import inspect
import unittest

from transformers import SwinConfig
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

from ...test_backbone_common import BackboneTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, _config_zero_init, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
	import torch
	from torch import nn

	from transformers import SwinBackbone, SwinForImageClassification, SwinForMaskedImageModeling, SwinModel
	from transformers.models.swin.modeling_swin import SWIN_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
	from PIL import Image

	from transformers import AutoImageProcessor





class __lowerCamelCase			:





	"""simple docstring"""






	def __init__(							self	,   UpperCAmelCase	,   UpperCAmelCase=13	,   UpperCAmelCase=32	,   UpperCAmelCase=2	,   UpperCAmelCase=3	,   UpperCAmelCase=16	,   UpperCAmelCase=[1, 2, 1]	,   UpperCAmelCase=[2, 2, 4]	,   UpperCAmelCase=2	,   UpperCAmelCase=2.0	,   UpperCAmelCase=True	,   UpperCAmelCase=0.0	,   UpperCAmelCase=0.0	,   UpperCAmelCase=0.1	,   UpperCAmelCase="gelu"	,   UpperCAmelCase=False	,   UpperCAmelCase=True	,   UpperCAmelCase=0.02	,   UpperCAmelCase=1e-5	,   UpperCAmelCase=True	,   UpperCAmelCase=None	,   UpperCAmelCase=True	,   UpperCAmelCase=10	,   UpperCAmelCase=8	,   UpperCAmelCase=["stage1", "stage2"]	,   UpperCAmelCase=[1, 2]	,   ):
							"""simple docstring"""







							_UpperCAmelCase     =      parent
							_UpperCAmelCase     =      batch_size
							_UpperCAmelCase     =      image_size
							_UpperCAmelCase     =      patch_size
							_UpperCAmelCase     =      num_channels
							_UpperCAmelCase     =      embed_dim
							_UpperCAmelCase     =      depths
							_UpperCAmelCase     =      num_heads
							_UpperCAmelCase     =      window_size
							_UpperCAmelCase     =      mlp_ratio
							_UpperCAmelCase     =      qkv_bias
							_UpperCAmelCase     =      hidden_dropout_prob
							_UpperCAmelCase     =      attention_probs_dropout_prob
							_UpperCAmelCase     =      drop_path_rate
							_UpperCAmelCase     =      hidden_act
							_UpperCAmelCase     =      use_absolute_embeddings
							_UpperCAmelCase     =      patch_norm
							_UpperCAmelCase     =      layer_norm_eps
							_UpperCAmelCase     =      initializer_range
							_UpperCAmelCase     =      is_training
							_UpperCAmelCase     =      scope
							_UpperCAmelCase     =      use_labels
							_UpperCAmelCase     =      type_sequence_label_size
							_UpperCAmelCase     =      encoder_stride
							_UpperCAmelCase     =      out_features
							_UpperCAmelCase     =      out_indices

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase     =      floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]   )

							_UpperCAmelCase     =      None
							if self.use_labels:
													_UpperCAmelCase     =      ids_tensor([self.batch_size]	,   self.type_sequence_label_size   )

							_UpperCAmelCase     =      self.get_config()

							return config, pixel_values, labels

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							return SwinConfig(
							    image_size=self.image_size	,   patch_size=self.patch_size	,   num_channels=self.num_channels	,   embed_dim=self.embed_dim	,   depths=self.depths	,   num_heads=self.num_heads	,   window_size=self.window_size	,   mlp_ratio=self.mlp_ratio	,   qkv_bias=self.qkv_bias	,   hidden_dropout_prob=self.hidden_dropout_prob	,   attention_probs_dropout_prob=self.attention_probs_dropout_prob	,   drop_path_rate=self.drop_path_rate	,   hidden_act=self.hidden_act	,   use_absolute_embeddings=self.use_absolute_embeddings	,   path_norm=self.patch_norm	,   layer_norm_eps=self.layer_norm_eps	,   initializer_range=self.initializer_range	,   encoder_stride=self.encoder_stride	,   out_features=self.out_features	,   out_indices=self.out_indices	,   )

	def 	UpperCamelCase   (							self	,   UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase   ):
							"""simple docstring"""







							_UpperCAmelCase     =      SwinModel(config=UpperCAmelCase   )
							model.to(UpperCAmelCase   )
							model.eval()
							_UpperCAmelCase     =      model(UpperCAmelCase   )

							_UpperCAmelCase     =      ((config.image_size // config.patch_size) ** 2) // (4 ** (len(config.depths   ) - 1))
							_UpperCAmelCase     =      int(config.embed_dim * 2 ** (len(config.depths   ) - 1)   )

							self.parent.assertEqual(result.last_hidden_state.shape	,   (self.batch_size, expected_seq_len, expected_dim)   )

	def 	UpperCamelCase   (							self	,   UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase   ):
							"""simple docstring"""







							_UpperCAmelCase     =      SwinBackbone(config=UpperCAmelCase   )
							model.to(UpperCAmelCase   )
							model.eval()
							_UpperCAmelCase     =      model(UpperCAmelCase   )

							# verify hidden states
							self.parent.assertEqual(len(result.feature_maps   )	,   len(config.out_features   )   )
							self.parent.assertListEqual(list(result.feature_maps[0].shape   )	,   [self.batch_size, model.channels[0], 16, 16]   )

							# verify channels
							self.parent.assertEqual(len(model.channels   )	,   len(config.out_features   )   )

							# verify backbone works with out_features=None
							_UpperCAmelCase     =      None
							_UpperCAmelCase     =      SwinBackbone(config=UpperCAmelCase   )
							model.to(UpperCAmelCase   )
							model.eval()
							_UpperCAmelCase     =      model(UpperCAmelCase   )

							# verify feature maps
							self.parent.assertEqual(len(result.feature_maps   )	,   1   )
							self.parent.assertListEqual(list(result.feature_maps[0].shape   )	,   [self.batch_size, model.channels[-1], 4, 4]   )

							# verify channels
							self.parent.assertEqual(len(model.channels   )	,   1   )

	def 	UpperCamelCase   (							self	,   UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase   ):
							"""simple docstring"""







							_UpperCAmelCase     =      SwinForMaskedImageModeling(config=UpperCAmelCase   )
							model.to(UpperCAmelCase   )
							model.eval()
							_UpperCAmelCase     =      model(UpperCAmelCase   )
							self.parent.assertEqual(
							    result.logits.shape	,   (self.batch_size, self.num_channels, self.image_size, self.image_size)   )

							# test greyscale images
							_UpperCAmelCase     =      1
							_UpperCAmelCase     =      SwinForMaskedImageModeling(UpperCAmelCase   )
							model.to(UpperCAmelCase   )
							model.eval()

							_UpperCAmelCase     =      floats_tensor([self.batch_size, 1, self.image_size, self.image_size]   )
							_UpperCAmelCase     =      model(UpperCAmelCase   )
							self.parent.assertEqual(result.logits.shape	,   (self.batch_size, 1, self.image_size, self.image_size)   )

	def 	UpperCamelCase   (							self	,   UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase   ):
							"""simple docstring"""







							_UpperCAmelCase     =      self.type_sequence_label_size
							_UpperCAmelCase     =      SwinForImageClassification(UpperCAmelCase   )
							model.to(UpperCAmelCase   )
							model.eval()
							_UpperCAmelCase     =      model(UpperCAmelCase	,   labels=UpperCAmelCase   )
							self.parent.assertEqual(result.logits.shape	,   (self.batch_size, self.type_sequence_label_size)   )

							# test greyscale images
							_UpperCAmelCase     =      1
							_UpperCAmelCase     =      SwinForImageClassification(UpperCAmelCase   )
							model.to(UpperCAmelCase   )
							model.eval()

							_UpperCAmelCase     =      floats_tensor([self.batch_size, 1, self.image_size, self.image_size]   )
							_UpperCAmelCase     =      model(UpperCAmelCase   )
							self.parent.assertEqual(result.logits.shape	,   (self.batch_size, self.type_sequence_label_size)   )

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase     =      self.prepare_config_and_inputs()
							(
							    (
							    _UpperCAmelCase						
							) ,			(
							    _UpperCAmelCase						
							) ,			(
							    _UpperCAmelCase						
							) ,									
							)     =      config_and_inputs
							_UpperCAmelCase     =      {'pixel_values': pixel_values}
							return config, inputs_dict





@require_torch
class __lowerCamelCase			(				A__					,	A__					,	unittest.TestCase):





	"""simple docstring"""






	UpperCamelCase__								=				(
	    (
	        SwinModel,
	        SwinBackbone,
	        SwinForImageClassification,
	        SwinForMaskedImageModeling,
	    )
	    if is_torch_available()
	    else ()
	)
	UpperCamelCase__								=				(
	    {"feature-extraction": SwinModel, "image-classification": SwinForImageClassification}
	    if is_torch_available()
	    else {}
	)
	UpperCamelCase__								=				True

	UpperCamelCase__								=				False
	UpperCamelCase__								=				False
	UpperCamelCase__								=				False

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase     =      SwinModelTester(self   )
							_UpperCAmelCase     =      ConfigTester(self	,   config_class=UpperCAmelCase	,   embed_dim=37   )

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							self.create_and_test_config_common_properties()
							self.config_tester.create_and_test_config_to_json_string()
							self.config_tester.create_and_test_config_to_json_file()
							self.config_tester.create_and_test_config_from_and_save_pretrained()
							self.config_tester.create_and_test_config_with_num_labels()
							self.config_tester.check_config_can_be_init_without_params()
							self.config_tester.check_config_arguments_init()

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							return

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase     =      self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_model(*UpperCAmelCase   )

	@unittest.skip(reason='Got `CUDA error: misaligned address` with PyTorch 2.0.0.'   )
	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							pass

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							super().test_training_gradient_checkpointing()

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase     =      self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_backbone(*UpperCAmelCase   )

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase     =      self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_masked_image_modeling(*UpperCAmelCase   )

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase     =      self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_image_classification(*UpperCAmelCase   )

	@unittest.skip(reason='Swin does not use inputs_embeds'   )
	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							pass

	@unittest.skip(reason='Swin Transformer does not use feedforward chunking'   )
	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							pass

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase ,			_UpperCAmelCase     =      self.model_tester.prepare_config_and_inputs_for_common()

							for model_class in self.all_model_classes:
													_UpperCAmelCase     =      model_class(UpperCAmelCase   )
													self.assertIsInstance(model.get_input_embeddings()	,   (nn.Module)   )
													_UpperCAmelCase     =      model.get_output_embeddings()
													self.assertTrue(x is None or isinstance(UpperCAmelCase	,   nn.Linear   )   )

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase ,			_UpperCAmelCase     =      self.model_tester.prepare_config_and_inputs_for_common()

							for model_class in self.all_model_classes:
													_UpperCAmelCase     =      model_class(UpperCAmelCase   )
													_UpperCAmelCase     =      inspect.signature(model.forward   )
													# signature.parameters is an OrderedDict => so arg_names order is deterministic
													_UpperCAmelCase     =      [*signature.parameters.keys()]

													_UpperCAmelCase     =      ['pixel_values']
													self.assertListEqual(arg_names[:1]	,   UpperCAmelCase   )

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase ,			_UpperCAmelCase     =      self.model_tester.prepare_config_and_inputs_for_common()
							_UpperCAmelCase     =      True

							for model_class in self.all_model_classes:
													_UpperCAmelCase     =      True
													_UpperCAmelCase     =      False
													_UpperCAmelCase     =      True
													_UpperCAmelCase     =      model_class(UpperCAmelCase   )
													model.to(UpperCAmelCase   )
													model.eval()
													with torch.no_grad():
																			_UpperCAmelCase     =      model(**self._prepare_for_class(UpperCAmelCase	,   UpperCAmelCase   )   )
													_UpperCAmelCase     =      outputs.attentions
													_UpperCAmelCase     =      len(self.model_tester.depths   )
													self.assertEqual(len(UpperCAmelCase   )	,   UpperCAmelCase   )

													# check that output_attentions also work using config
													del inputs_dict["output_attentions"]
													_UpperCAmelCase     =      True
													_UpperCAmelCase     =      config.window_size**2
													_UpperCAmelCase     =      model_class(UpperCAmelCase   )
													model.to(UpperCAmelCase   )
													model.eval()
													with torch.no_grad():
																			_UpperCAmelCase     =      model(**self._prepare_for_class(UpperCAmelCase	,   UpperCAmelCase   )   )
													_UpperCAmelCase     =      outputs.attentions
													self.assertEqual(len(UpperCAmelCase   )	,   UpperCAmelCase   )

													self.assertListEqual(
													    list(attentions[0].shape[-3:]   )	,   [self.model_tester.num_heads[0], window_size_squared, window_size_squared]	,   )
													_UpperCAmelCase     =      len(UpperCAmelCase   )

													# Check attention is always last and order is fine
													_UpperCAmelCase     =      True
													_UpperCAmelCase     =      True
													_UpperCAmelCase     =      model_class(UpperCAmelCase   )
													model.to(UpperCAmelCase   )
													model.eval()
													with torch.no_grad():
																			_UpperCAmelCase     =      model(**self._prepare_for_class(UpperCAmelCase	,   UpperCAmelCase   )   )

													# also another +1 for reshaped_hidden_states
													_UpperCAmelCase     =      1 if model_class.__name__ == 'SwinBackbone' else 2
													self.assertEqual(out_len + added_hidden_states	,   len(UpperCAmelCase   )   )

													_UpperCAmelCase     =      outputs.attentions

													self.assertEqual(len(UpperCAmelCase   )	,   UpperCAmelCase   )

													self.assertListEqual(
													    list(self_attentions[0].shape[-3:]   )	,   [self.model_tester.num_heads[0], window_size_squared, window_size_squared]	,   )

	def 	UpperCamelCase   (							self	,   UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase   ):
							"""simple docstring"""







							_UpperCAmelCase     =      model_class(UpperCAmelCase   )
							model.to(UpperCAmelCase   )
							model.eval()

							with torch.no_grad():
													_UpperCAmelCase     =      model(**self._prepare_for_class(UpperCAmelCase	,   UpperCAmelCase   )   )

							_UpperCAmelCase     =      outputs.hidden_states

							_UpperCAmelCase     =      getattr(
							    self.model_tester	,   'expected_num_hidden_layers'	,   len(self.model_tester.depths   ) + 1   )
							self.assertEqual(len(UpperCAmelCase   )	,   UpperCAmelCase   )

							# Swin has a different seq_length
							_UpperCAmelCase     =      (
							    config.patch_size
							    if isinstance(config.patch_size	,   collections.abc.Iterable   )
							    else (config.patch_size, config.patch_size)
							)

							_UpperCAmelCase     =      (image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])

							self.assertListEqual(
							    list(hidden_states[0].shape[-2:]   )	,   [num_patches, self.model_tester.embed_dim]	,   )

							if not model_class.__name__ == "SwinBackbone":
													_UpperCAmelCase     =      outputs.reshaped_hidden_states
													self.assertEqual(len(UpperCAmelCase   )	,   UpperCAmelCase   )

													_UpperCAmelCase ,			_UpperCAmelCase ,			_UpperCAmelCase ,			_UpperCAmelCase     =      reshaped_hidden_states[0].shape
													_UpperCAmelCase     =      (
													    reshaped_hidden_states[0].view(UpperCAmelCase	,   UpperCAmelCase	,   height * width   ).permute(0	,   2	,   1   )
													)
													self.assertListEqual(
													    list(reshaped_hidden_states.shape[-2:]   )	,   [num_patches, self.model_tester.embed_dim]	,   )

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase ,			_UpperCAmelCase     =      self.model_tester.prepare_config_and_inputs_for_common()

							_UpperCAmelCase     =      (
							    self.model_tester.image_size
							    if isinstance(self.model_tester.image_size	,   collections.abc.Iterable   )
							    else (self.model_tester.image_size, self.model_tester.image_size)
							)

							for model_class in self.all_model_classes:
													_UpperCAmelCase     =      True
													self.check_hidden_states_output(UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase   )

													# check that output_hidden_states also work using config
													del inputs_dict["output_hidden_states"]
													_UpperCAmelCase     =      True

													self.check_hidden_states_output(UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase   )

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase ,			_UpperCAmelCase     =      self.model_tester.prepare_config_and_inputs_for_common()
							_UpperCAmelCase     =      3

							_UpperCAmelCase     =      (
							    self.model_tester.image_size
							    if isinstance(self.model_tester.image_size	,   collections.abc.Iterable   )
							    else (self.model_tester.image_size, self.model_tester.image_size)
							)
							_UpperCAmelCase     =      (
							    config.patch_size
							    if isinstance(config.patch_size	,   collections.abc.Iterable   )
							    else (config.patch_size, config.patch_size)
							)

							_UpperCAmelCase     =      image_size[0] + patch_size[0] - (image_size[0] % patch_size[0])
							_UpperCAmelCase     =      image_size[1] + patch_size[1] - (image_size[1] % patch_size[1])

							for model_class in self.all_model_classes:
													_UpperCAmelCase     =      True
													self.check_hidden_states_output(UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase	,   (padded_height, padded_width)   )

													# check that output_hidden_states also work using config
													del inputs_dict["output_hidden_states"]
													_UpperCAmelCase     =      True
													self.check_hidden_states_output(UpperCAmelCase	,   UpperCAmelCase	,   UpperCAmelCase	,   (padded_height, padded_width)   )

	@slow
	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							for model_name in SWIN_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
													_UpperCAmelCase     =      SwinModel.from_pretrained(UpperCAmelCase   )
													self.assertIsNotNone(UpperCAmelCase   )

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase ,			_UpperCAmelCase     =      self.model_tester.prepare_config_and_inputs_for_common()

							_UpperCAmelCase     =      _config_zero_init(UpperCAmelCase   )
							for model_class in self.all_model_classes:
													_UpperCAmelCase     =      model_class(config=UpperCAmelCase   )
													for name, param in model.named_parameters():
																			if "embeddings" not in name and param.requires_grad:
																									self.assertIn(
																									    ((param.data.mean() * 1e9).round() / 1e9).item()	,   [0.0, 1.0]	,   msg=F"""Parameter {name} of model {model_class} seems not properly initialized"""	,   )





@require_vision
@require_torch
class __lowerCamelCase			(				unittest.TestCase):





	"""simple docstring"""






	@cached_property
	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							return (
							    AutoImageProcessor.from_pretrained('microsoft/swin-tiny-patch4-window7-224'   )
							    if is_vision_available()
							    else None
							)

	@slow
	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase     =      SwinForImageClassification.from_pretrained('microsoft/swin-tiny-patch4-window7-224'   ).to(UpperCAmelCase   )
							_UpperCAmelCase     =      self.default_image_processor

							_UpperCAmelCase     =      Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png'   )
							_UpperCAmelCase     =      image_processor(images=UpperCAmelCase	,   return_tensors='pt'   ).to(UpperCAmelCase   )

							# forward pass
							with torch.no_grad():
													_UpperCAmelCase     =      model(**UpperCAmelCase   )

							# verify the logits
							_UpperCAmelCase     =      torch.Size((1, 1000)   )
							self.assertEqual(outputs.logits.shape	,   UpperCAmelCase   )
							_UpperCAmelCase     =      torch.tensor([-0.09_48, -0.64_54, -0.09_21]   ).to(UpperCAmelCase   )
							self.assertTrue(torch.allclose(outputs.logits[0, :3]	,   UpperCAmelCase	,   atol=1e-4   )   )





@require_torch
class __lowerCamelCase			(				unittest.TestCase					,	A__):





	"""simple docstring"""






	UpperCamelCase__								=				(SwinBackbone,) if is_torch_available() else ()
	UpperCamelCase__								=				SwinConfig

	def 	UpperCamelCase   (							self   ):
							"""simple docstring"""







							_UpperCAmelCase     =      SwinModelTester(self   )








from __future__ import annotations

_a				     =  [2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]





class __lowerCamelCase			:





	"""simple docstring"""






	def __init__(							self	,   UpperCAmelCase   ):
							"""simple docstring"""







							_UpperCAmelCase     =      -1
							_UpperCAmelCase     =      -1
							_UpperCAmelCase     =      [-1] * length
							_UpperCAmelCase     =      None
							_UpperCAmelCase     =      None

	def __repr__(							self   ):
							"""simple docstring"""







							return F"""Node(min_value={self.minn} max_value={self.maxx})"""



def __A   (				__lowerCAmelCase     )->  Node | None:





						"""simple docstring"""



						_UpperCAmelCase     =      Node(len(__lowerCAmelCase     )     )
						_UpperCAmelCase ,			_UpperCAmelCase     =      min(__lowerCAmelCase     ), max(__lowerCAmelCase     )
						# Leaf node case where the node contains only one unique value
						if root.minn == root.maxx:
												return root
						_UpperCAmelCase     =      (root.minn + root.maxx) // 2

						_UpperCAmelCase     =      []
						_UpperCAmelCase     =      []

						for index, num in enumerate(__lowerCAmelCase     ):
												if num <= pivot:
																		left_arr.append(__lowerCAmelCase     )
												else:
																		right_arr.append(__lowerCAmelCase     )
												_UpperCAmelCase     =      len(__lowerCAmelCase     )
						_UpperCAmelCase     =      build_tree(__lowerCAmelCase     )
						_UpperCAmelCase     =      build_tree(__lowerCAmelCase     )
						return root


def __A   (				__lowerCAmelCase			,		__lowerCAmelCase			,		__lowerCAmelCase     )->  int:





						"""simple docstring"""



						if index < 0 or node is None:
												return 0
						# Leaf node cases
						if node.minn == node.maxx:
												return index + 1 if node.minn == num else 0
						_UpperCAmelCase     =      (node.minn + node.maxx) // 2
						if num <= pivot:
												# go the left subtree and map index to the left subtree
												return rank_till_index(node.left			,		__lowerCAmelCase			,		node.map_left[index] - 1     )
						else:
												# go to the right subtree and map index to the right subtree
												return rank_till_index(node.right			,		__lowerCAmelCase			,		index - node.map_left[index]     )


def __A   (				__lowerCAmelCase			,		__lowerCAmelCase			,		__lowerCAmelCase			,		__lowerCAmelCase     )->  int:





						"""simple docstring"""



						if start > end:
												return 0
						_UpperCAmelCase     =      rank_till_index(__lowerCAmelCase			,		__lowerCAmelCase			,		__lowerCAmelCase     )
						_UpperCAmelCase     =      rank_till_index(__lowerCAmelCase			,		__lowerCAmelCase			,		start - 1     )
						return rank_till_end - rank_before_start


def __A   (				__lowerCAmelCase			,		__lowerCAmelCase			,		__lowerCAmelCase			,		__lowerCAmelCase     )->  int:





						"""simple docstring"""



						if index > (end - start) or start > end or node is None:
												return -1
						# Leaf node case
						if node.minn == node.maxx:
												return node.minn
						# Number of elements in the left subtree in interval [start, end]
						_UpperCAmelCase     =      node.map_left[end] - (
						    node.map_left[start - 1] if start else 0
						)
						if num_elements_in_left_tree > index:
												return quantile(
												    node.left			,		__lowerCAmelCase			,		(node.map_left[start - 1] if start else 0)			,		node.map_left[end] - 1			,		)
						else:
												return quantile(
												    node.right			,		index - num_elements_in_left_tree			,		start - (node.map_left[start - 1] if start else 0)			,		end - node.map_left[end]			,		)


def __A   (				__lowerCAmelCase			,		__lowerCAmelCase			,		__lowerCAmelCase			,		__lowerCAmelCase			,		__lowerCAmelCase     )->  int:





						"""simple docstring"""



						if (
						    start > end
						    or node is None
						    or start_num > end_num
						    or node.minn > end_num
						    or node.maxx < start_num
						):
												return 0
						if start_num <= node.minn and node.maxx <= end_num:
												return end - start + 1
						_UpperCAmelCase     =      range_counting(
						    node.left			,		(node.map_left[start - 1] if start else 0)			,		node.map_left[end] - 1			,		__lowerCAmelCase			,		__lowerCAmelCase			,		)
						_UpperCAmelCase     =      range_counting(
						    node.right			,		start - (node.map_left[start - 1] if start else 0)			,		end - node.map_left[end]			,		__lowerCAmelCase			,		__lowerCAmelCase			,		)
						return left + right


if __name__ == "__main__":
		import doctest

		doctest.testmod()
