




import os
from pickle import UnpicklingError
from typing import Dict, Tuple

import jax
import jax.numpy as jnp
import numpy as np
from flax.serialization import from_bytes
from flax.traverse_util import flatten_dict, unflatten_dict

import transformers

from .utils import logging


__UpperCamelCase   :			int          = logging.get_logger(__name__)





def 						__A						(      __lowerCamelCase				,     __lowerCamelCase				,     __lowerCamelCase				,     __lowerCamelCase=False       ) ->			List[Any]:
	try:
		import torch  # noqa: F401
	except ImportError:
		logger.error(
		    """Loading a PyTorch model in Flax, requires both PyTorch and Flax to be installed. Please see"""
		    """ https://pytorch.org/ and https://flax.readthedocs.io/en/latest/installation.html for installation"""
		    """ instructions."""       )
		raise

	if not is_sharded:
		a									=				os.path.abspath(__lowerCamelCase       )
		logger.info(f'Loading PyTorch weights from {pt_path}'       )

		a									=				torch.load(__lowerCamelCase				,     map_location="""cpu"""       )
		logger.info(f'PyTorch checkpoint contains {sum(t.numel() for t in pt_state_dict.values()       ):,} parameters.'       )

		a									=				convert_pytorch_state_dict_to_flax(__lowerCamelCase				,     __lowerCamelCase       )
	else:
		# model is sharded and pytorch_checkpoint_path already contains the list of .pt shard files
		a									=				convert_pytorch_sharded_state_dict_to_flax(__lowerCamelCase				,     __lowerCamelCase       )
	return flax_state_dict





def 						__A						(      __lowerCamelCase				,     __lowerCamelCase				,     __lowerCamelCase				,     __lowerCamelCase				,     ) ->			(Tuple[str], np.ndarray):

	def is_key_or_prefix_key_in_dict(__lowerCamelCase       ) -> bool:
		return len(set(__lowerCamelCase       ) & {key, (model_prefix,) + key}       ) > 0

	# layer norm
	a									=				pt_tuple_key[:-1] + ("""scale""",)
	if pt_tuple_key[-1] in ["weight", "gamma"] and is_key_or_prefix_key_in_dict(__lowerCamelCase       ):
		return renamed_pt_tuple_key, pt_tensor

	# batch norm layer mean
	a									=				pt_tuple_key[:-1] + ("""mean""",)
	if pt_tuple_key[-1] == "running_mean" and not is_key_or_prefix_key_in_dict(__lowerCamelCase       ):
		return renamed_pt_tuple_key, pt_tensor

	# batch norm layer var
	a									=				pt_tuple_key[:-1] + ("""var""",)
	if pt_tuple_key[-1] == "running_var" and not is_key_or_prefix_key_in_dict(__lowerCamelCase       ):
		return renamed_pt_tuple_key, pt_tensor

	# embedding
	a									=				pt_tuple_key[:-1] + ("""embedding""",)
	if pt_tuple_key[-1] == "weight" and is_key_or_prefix_key_in_dict(__lowerCamelCase       ):
		return renamed_pt_tuple_key, pt_tensor

	# conv layer
	a									=				pt_tuple_key[:-1] + ("""kernel""",)
	if pt_tuple_key[-1] == "weight" and pt_tensor.ndim == 4 and not is_key_or_prefix_key_in_dict(__lowerCamelCase       ):
		a									=				pt_tensor.transpose(2				,     3				,     1				,     0       )
		return renamed_pt_tuple_key, pt_tensor

	# linear layer
	a									=				pt_tuple_key[:-1] + ("""kernel""",)
	if pt_tuple_key[-1] == "weight" and not is_key_or_prefix_key_in_dict(__lowerCamelCase       ):
		a									=				pt_tensor.T
		return renamed_pt_tuple_key, pt_tensor

	# old PyTorch layer norm weight
	a									=				pt_tuple_key[:-1] + ("""weight""",)
	if pt_tuple_key[-1] == "gamma":
		return renamed_pt_tuple_key, pt_tensor

	# old PyTorch layer norm bias
	a									=				pt_tuple_key[:-1] + ("""bias""",)
	if pt_tuple_key[-1] == "beta":
		return renamed_pt_tuple_key, pt_tensor

	# New `weight_norm` from https://github.com/huggingface/transformers/pull/24030
	a									=				None
	if pt_tuple_key[-3::2] == ("parametrizations", "original0"):
		a									=				pt_tuple_key[-2] + """_g"""
	elif pt_tuple_key[-3::2] == ("parametrizations", "original1"):
		a									=				pt_tuple_key[-2] + """_v"""
	if name is not None:
		a									=				pt_tuple_key[:-3] + (name,)
		return renamed_pt_tuple_key, pt_tensor

	return pt_tuple_key, pt_tensor





def 						__A						(      __lowerCamelCase				,     __lowerCamelCase       ) ->			Optional[Any]:
	# convert pytorch tensor to numpy
	a									=				{k: v.numpy() for k, v in pt_state_dict.items()}

	a									=				flax_model.base_model_prefix

	# use params dict if the model contains batch norm layers
	if "params" in flax_model.params:
		a									=				flax_model.params["""params"""]
	else:
		a									=				flax_model.params
	a									=				flatten_dict(__lowerCamelCase       )

	# add batch_stats keys,values to dict
	if "batch_stats" in flax_model.params:
		a									=				flatten_dict(flax_model.params["""batch_stats"""]       )
		random_flax_state_dict.update(__lowerCamelCase       )

	a									=				{}

	a									=				(model_prefix not in flax_model_params) and (
	    model_prefix in {k.split("""."""       )[0] for k in pt_state_dict.keys()}
	)
	a									=				(model_prefix in flax_model_params) and (
	    model_prefix not in {k.split("""."""       )[0] for k in pt_state_dict.keys()}
	)

	# Need to change some parameters name to match Flax names
	for pt_key, pt_tensor in pt_state_dict.items():
		a									=				tuple(pt_key.split("""."""       )       )

		# remove base model prefix if necessary
		a									=				pt_tuple_key[0] == model_prefix
		if load_model_with_head_into_base_model and has_base_model_prefix:
			a									=				pt_tuple_key[1:]

		# Correctly rename weight parameters
		a							,					a									=				rename_key_and_reshape_tensor(
		    __lowerCamelCase				,     __lowerCamelCase				,     __lowerCamelCase				,     __lowerCamelCase       )

		# add model prefix if necessary
		a									=				(model_prefix,) + flax_key in random_flax_state_dict
		if load_base_model_into_model_with_head and require_base_model_prefix:
			a									=				(model_prefix,) + flax_key

		if flax_key in random_flax_state_dict:
			if flax_tensor.shape != random_flax_state_dict[flax_key].shape:
				raise ValueError(
				    f'PyTorch checkpoint seems to be incorrect. Weight {pt_key} was expected to be of shape '
				    f'{random_flax_state_dict[flax_key].shape}, but is {flax_tensor.shape}.'       )

        # add batch stats if the model contains batchnorm layers
		if "batch_stats" in flax_model.params:
			if "mean" in flax_key[-1] or "var" in flax_key[-1]:
				a									=				jnp.asarray(__lowerCamelCase       )
				continue
			# remove num_batches_tracked key
			if "num_batches_tracked" in flax_key[-1]:
				flax_state_dict.pop(__lowerCamelCase				,     __lowerCamelCase       )
				continue

			# also add unexpected weight so that warning is thrown
			a									=				jnp.asarray(__lowerCamelCase       )

		else:
			# also add unexpected weight so that warning is thrown
			a									=				jnp.asarray(__lowerCamelCase       )

	return unflatten_dict(__lowerCamelCase       )





def 						__A						(      __lowerCamelCase				,     __lowerCamelCase       ) ->			Any:
	import torch

	# Load the index
	a									=				{}
	for shard_file in shard_filenames:
		# load using msgpack utils
		a									=				torch.load(__lowerCamelCase       )
		a									=				{k: v.numpy() for k, v in pt_state_dict.items()}

		a									=				flax_model.base_model_prefix

		# use params dict if the model contains batch norm layers and then add batch_stats keys,values to dict
		if "batch_stats" in flax_model.params:
			a									=				flax_model.params["""params"""]

			a									=				flatten_dict(__lowerCamelCase       )
			random_flax_state_dict.update(flatten_dict(flax_model.params["""batch_stats"""]       )       )
		else:
			a									=				flax_model.params
			a									=				flatten_dict(__lowerCamelCase       )

		a									=				(model_prefix not in flax_model_params) and (
		    model_prefix in {k.split("""."""       )[0] for k in pt_state_dict.keys()}
		)
		a									=				(model_prefix in flax_model_params) and (
		    model_prefix not in {k.split("""."""       )[0] for k in pt_state_dict.keys()}
		)
		# Need to change some parameters name to match Flax names
		for pt_key, pt_tensor in pt_state_dict.items():
			a									=				tuple(pt_key.split("""."""       )       )

			# remove base model prefix if necessary
			a									=				pt_tuple_key[0] == model_prefix
			if load_model_with_head_into_base_model and has_base_model_prefix:
				a									=				pt_tuple_key[1:]

			# Correctly rename weight parameters
			a							,					a									=				rename_key_and_reshape_tensor(
			    __lowerCamelCase				,     __lowerCamelCase				,     __lowerCamelCase				,     __lowerCamelCase       )
			# add model prefix if necessary
			a									=				(model_prefix,) + flax_key in random_flax_state_dict
			if load_base_model_into_model_with_head and require_base_model_prefix:
				a									=				(model_prefix,) + flax_key

			if flax_key in random_flax_state_dict:
				if flax_tensor.shape != random_flax_state_dict[flax_key].shape:
					raise ValueError(
					    f'PyTorch checkpoint seems to be incorrect. Weight {pt_key} was expected to be of shape '
					    f'{random_flax_state_dict[flax_key].shape}, but is {flax_tensor.shape}.'       )

            # add batch stats if the model contains batchnorm layers
			if "batch_stats" in flax_model.params:
				if "mean" in flax_key[-1]:
					a									=				jnp.asarray(__lowerCamelCase       )
					continue
				if "var" in flax_key[-1]:
					a									=				jnp.asarray(__lowerCamelCase       )
					continue
				# remove num_batches_tracked key
				if "num_batches_tracked" in flax_key[-1]:
					flax_state_dict.pop(__lowerCamelCase				,     __lowerCamelCase       )
					continue

				# also add unexpected weight so that warning is thrown
				a									=				jnp.asarray(__lowerCamelCase       )

			else:
				# also add unexpected weight so that warning is thrown
				a									=				jnp.asarray(__lowerCamelCase       )
	return unflatten_dict(__lowerCamelCase       )





def 						__A						(      __lowerCamelCase				,     __lowerCamelCase       ) ->			Any:
	a									=				os.path.abspath(__lowerCamelCase       )
	logger.info(f'Loading Flax weights from {flax_checkpoint_path}'       )

	# import correct flax class
	a									=				getattr(__lowerCamelCase				,     """Flax""" + model.__class__.__name__       )

	# load flax weight dict
	with open(__lowerCamelCase				,     """rb"""       ) as state_f:
		try:
			a									=				from_bytes(__lowerCamelCase				,     state_f.read()       )
		except UnpicklingError:
			raise EnvironmentError(f'Unable to convert {flax_checkpoint_path} to Flax deserializable object. '       )

	return load_flax_weights_in_pytorch_model(__lowerCamelCase				,     __lowerCamelCase       )





def 						__A						(      __lowerCamelCase				,     __lowerCamelCase       ) ->			Optional[int]:

	try:
		import torch  # noqa: F401
	except ImportError:
		logger.error(
		    """Loading a Flax weights in PyTorch, requires both PyTorch and Flax to be installed. Please see"""
		    """ https://pytorch.org/ and https://flax.readthedocs.io/en/latest/installation.html for installation"""
		    """ instructions."""       )
		raise

	# check if we have bf16 weights
	a									=				flatten_dict(jax.tree_util.tree_map(lambda __lowerCamelCase       : x.dtype == jnp.bfloataa				,     __lowerCamelCase       )       ).values()
	if any(__lowerCamelCase       ):
		# convert all weights to fp32 if the are bf16 since torch.from_numpy can-not handle bf16
		# and bf16 is not fully supported in PT yet.
		logger.warning(
		    """Found ``bfloat16`` weights in Flax model. Casting all ``bfloat16`` weights to ``float32`` """
		    """before loading those in PyTorch model."""       )
		a									=				jax.tree_util.tree_map(
		    lambda __lowerCamelCase       : params.astype(np.floataa       ) if params.dtype == jnp.bfloataa else params				,     __lowerCamelCase       )

	a									=				flatten_dict(__lowerCamelCase       )
	a									=				pt_model.state_dict()

	a									=				(pt_model.base_model_prefix in flax_state) and (
	    pt_model.base_model_prefix not in {k.split("""."""       )[0] for k in pt_model_dict.keys()}
	)
	a									=				(pt_model.base_model_prefix not in flax_state) and (
	    pt_model.base_model_prefix in {k.split("""."""       )[0] for k in pt_model_dict.keys()}
	)

	# keep track of unexpected & missing keys
	a									=				[]
	a									=				set(pt_model_dict.keys()       )

	for flax_key_tuple, flax_tensor in flax_state_dict.items():
		a									=				flax_key_tuple[0] == pt_model.base_model_prefix
		a									=				""".""".join((pt_model.base_model_prefix,) + flax_key_tuple       ) in pt_model_dict

		# adapt flax_key to prepare for loading from/to base model only
		if load_model_with_head_into_base_model and has_base_model_prefix:
			a									=				flax_key_tuple[1:]
		elif load_base_model_into_model_with_head and require_base_model_prefix:
			a									=				(pt_model.base_model_prefix,) + flax_key_tuple

		# rename flax weights to PyTorch format
		if flax_key_tuple[-1] == "kernel" and flax_tensor.ndim == 4 and ".".join(__lowerCamelCase       ) not in pt_model_dict:
			# conv layer
			a									=				flax_key_tuple[:-1] + ("""weight""",)
			a									=				jnp.transpose(__lowerCamelCase				,     (3, 2, 0, 1)       )
		elif flax_key_tuple[-1] == "kernel" and ".".join(__lowerCamelCase       ) not in pt_model_dict:
			# linear layer
			a									=				flax_key_tuple[:-1] + ("""weight""",)
			a									=				flax_tensor.T
		elif flax_key_tuple[-1] in ["scale", "embedding"]:
			a									=				flax_key_tuple[:-1] + ("""weight""",)

		# adding batch stats from flax batch norm to pt
		elif "mean" in flax_key_tuple[-1]:
			a									=				flax_key_tuple[:-1] + ("""running_mean""",)
		elif "var" in flax_key_tuple[-1]:
			a									=				flax_key_tuple[:-1] + ("""running_var""",)

		if "batch_stats" in flax_state:
			a									=				""".""".join(flax_key_tuple[1:]       )  # Remove the params/batch_stats header
		else:
			a									=				""".""".join(__lowerCamelCase       )

		# We also need to look at `pt_model_dict` and see if there are keys requiring further transformation.
		a									=				{}
		# New `weight_norm` from https://github.com/huggingface/transformers/pull/24030
		for key in pt_model_dict:
			a									=				key.split("""."""       )
			a									=				None
			if key_components[-3::2] == ["parametrizations", "original0"]:
				a									=				key_components[-2] + """_g"""
			elif key_components[-3::2] == ["parametrizations", "original1"]:
				a									=				key_components[-2] + """_v"""
			if name is not None:
				a									=				key_components[:-3] + [name]
				a									=				""".""".join(__lowerCamelCase       )
				a									=				key

		if flax_key in special_pt_names:
			a									=				special_pt_names[flax_key]

		if flax_key in pt_model_dict:
			if flax_tensor.shape != pt_model_dict[flax_key].shape:
				raise ValueError(
				    f'Flax checkpoint seems to be incorrect. Weight {flax_key_tuple} was expected '
				    f'to be of shape {pt_model_dict[flax_key].shape}, but is {flax_tensor.shape}.'       )
			else:
				# add weight to pytorch dict
				a									=				np.asarray(__lowerCamelCase       ) if not isinstance(__lowerCamelCase				,     np.ndarray       ) else flax_tensor
				a									=				torch.from_numpy(__lowerCamelCase       )
				# remove from missing keys
				missing_keys.remove(__lowerCamelCase       )
		else:
			# weight is not expected by PyTorch model
			unexpected_keys.append(__lowerCamelCase       )

	pt_model.load_state_dict(__lowerCamelCase       )

	# re-transform missing_keys to list
	a									=				list(__lowerCamelCase       )

	if len(__lowerCamelCase       ) > 0:
		logger.warning(
		    """Some weights of the Flax model were not used when initializing the PyTorch model"""
		    f' {pt_model.__class__.__name__}: {unexpected_keys}\n- This IS expected if you are initializing'
		    f' {pt_model.__class__.__name__} from a Flax model trained on another task or with another architecture'
		    """ (e.g. initializing a BertForSequenceClassification model from a FlaxBertForPreTraining model).\n- This"""
		    f' IS NOT expected if you are initializing {pt_model.__class__.__name__} from a Flax model that you expect'
		    """ to be exactly identical (e.g. initializing a BertForSequenceClassification model from a"""
		    """ FlaxBertForSequenceClassification model)."""       )
	else:
		logger.warning(f'All Flax model weights were used when initializing {pt_model.__class__.__name__}.\n'       )
	if len(__lowerCamelCase       ) > 0:
		logger.warning(
		    f'Some weights of {pt_model.__class__.__name__} were not initialized from the Flax model and are newly'
		    f' initialized: {missing_keys}\nYou should probably TRAIN this model on a down-stream task to be able to'
		    """ use it for predictions and inference."""       )
	else:
		logger.warning(
		    f'All the weights of {pt_model.__class__.__name__} were initialized from the Flax model.\n'
		    """If your task is similar to the task the model of the checkpoint was trained on, """
		    f'you can already use {pt_model.__class__.__name__} for predictions without further training.'       )

	return pt_model







def 						__A						(      ) ->			list[list[int]]:
	return [list(range(1000 - i				,     -1000 - i				,     -1       )       ) for i in range(1000       )]


__UpperCamelCase   :			str          = generate_large_matrix()
__UpperCamelCase   :			Tuple          = (
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)





def 						__A						(      __lowerCamelCase       ) ->			None:
	assert all(row == sorted(__lowerCamelCase				,     reverse=__lowerCamelCase       ) for row in grid       )
	assert all(list(__lowerCamelCase       ) == sorted(__lowerCamelCase				,     reverse=__lowerCamelCase       ) for col in zip(*__lowerCamelCase       )       )





def 						__A						(      __lowerCamelCase       ) ->			int:
	a									=				0
	a									=				len(__lowerCamelCase       ) - 1

	# Edge cases such as no values or all numbers are negative.
	if not array or array[0] < 0:
		return 0

	while right + 1 > left:
		a									=				(left + right) // 2
		a									=				array[mid]

		# Num must be negative and the index must be greater than or equal to 0.
		if num < 0 and array[mid - 1] >= 0:
			return mid

		if num >= 0:
			a									=				mid + 1
		else:
			a									=				mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
	return len(__lowerCamelCase       )





def 						__A						(      __lowerCamelCase       ) ->			int:
	a									=				0
	a									=				len(grid[0]       )

	for i in range(len(__lowerCamelCase       )       ):
		a									=				find_negative_index(grid[i][:bound]       )
		total += bound
	return (len(__lowerCamelCase       ) * len(grid[0]       )) - total





def 						__A						(      __lowerCamelCase       ) ->			int:
	return len([number for row in grid for number in row if number < 0]       )





def 						__A						(      __lowerCamelCase       ) ->			int:
	a									=				0
	for row in grid:
		for i, number in enumerate(__lowerCamelCase       ):
			if number < 0:
				total += len(__lowerCamelCase       ) - i
				break
	return total





def 						__A						(      ) ->			None:
	from timeit import timeit

	print("""Running benchmarks"""       )
	a									=				(
	    """from __main__ import count_negatives_binary_search, """
	    """count_negatives_brute_force, count_negatives_brute_force_with_break, grid"""
	)
	for func in (
	    "count_negatives_binary_search",  # took 0.7727 seconds
	    "count_negatives_brute_force_with_break",  # took 4.6505 seconds
	    "count_negatives_brute_force",  # took 12.8160 seconds
	):
		a									=				timeit(f'{func}(grid=grid)'				,     setup=__lowerCamelCase				,     number=500       )
		print(f'{func}() took {time:0.4f} seconds'       )


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		benchmark()

