

'''simple docstring'''





import logging
import math
from functools import partial
from typing import Any, Callable, Dict, Iterable, List, Optional, Sequence, Tuple, Union

import torch

from .tensor_utils import tensor_tree_map, tree_map







def   _UpperCamelCase	(		__UpperCamelCase	)       ->			List[Tuple[int, ...]]:
					lowerCamelCase_  				=      []
					if isinstance(__UpperCamelCase    ,__UpperCamelCase	):
										for v in tree.values():
															shapes.extend(_fetch_dims(__UpperCamelCase	)	)
					elif isinstance(__UpperCamelCase    ,(list, tuple)	):
										for t in tree:
															shapes.extend(_fetch_dims(__UpperCamelCase	)	)
					elif isinstance(__UpperCamelCase    ,torch.Tensor	):
										shapes.append(tree.shape	)
					else:
										raise ValueError('Not supported'	)

					return shapes







@torch.jit.ignore
def   _UpperCamelCase	(		__UpperCamelCase    ,__UpperCamelCase	)       ->			Tuple[int, ...]:
					lowerCamelCase_  				=      []
					for d in reversed(__UpperCamelCase	):
										idx.append(flat_idx % d	)
										lowerCamelCase_  				=      flat_idx // d

					return tuple(reversed(__UpperCamelCase	)	)







@torch.jit.ignore
def   _UpperCamelCase	(		__UpperCamelCase    ,__UpperCamelCase    ,__UpperCamelCase    ,__UpperCamelCase = None    ,__UpperCamelCase = None    ,)       ->			List[Tuple[slice, ...]]:

					# start_edges and end_edges both indicate whether, starting from any given
					# dimension, the start/end index is at the top/bottom edge of the
					# corresponding tensor, modeled as a tree
					def reduce_edge_list(__UpperCamelCase	) -> None:
										lowerCamelCase_  				=      True
										for i in range(len(__UpperCamelCase	)	):
															lowerCamelCase_  				=      -1 * (i + 1)
															l[reversed_idx] &= tally
															lowerCamelCase_  				=      l[reversed_idx]

					if start_edges is None:
										lowerCamelCase_  				=      [s == 0 for s in start]
										reduce_edge_list(__UpperCamelCase	)
					if end_edges is None:
										lowerCamelCase_  				=      [e == (d - 1) for e, d in zip(__UpperCamelCase    ,__UpperCamelCase	)]
										reduce_edge_list(__UpperCamelCase	)

					# Base cases. Either start/end are empty and we're done, or the final,
					# one-dimensional tensor can be simply sliced
					if len(__UpperCamelCase	) == 0:
										return [()]
					elif len(__UpperCamelCase	) == 1:
										return [(slice(start[0]    ,end[0] + 1	),)]

					lowerCamelCase_  				=      []
					lowerCamelCase_  				=      []

					# Dimensions common to start and end can be selected directly
					for s, e in zip(__UpperCamelCase    ,__UpperCamelCase	):
										if s == e:
															path_list.append(slice(__UpperCamelCase    ,s + 1	)	)
										else:
															break

					lowerCamelCase_  				=      tuple(__UpperCamelCase	)
					lowerCamelCase_  				=      len(__UpperCamelCase	)

					# start == end, and we're done
					if divergence_idx == len(__UpperCamelCase	):
										return [path]

					def upper() -> Tuple[Tuple[slice, ...], ...]:
										assert start_edges is not None
										assert end_edges is not None

										lowerCamelCase_  				=      start[divergence_idx]
										return tuple(
										    path + (slice(__UpperCamelCase    ,sdi + 1	),) + s
										    for s in _get_minimal_slice_set(
										        start[divergence_idx + 1 :]    ,[d - 1 for d in dims[divergence_idx + 1 :]]    ,dims[divergence_idx + 1 :]    ,start_edges=start_edges[divergence_idx + 1 :]    ,end_edges=[True for _ in end_edges[divergence_idx + 1 :]]    ,)	)

					def lower() -> Tuple[Tuple[slice, ...], ...]:
										assert start_edges is not None
										assert end_edges is not None

										lowerCamelCase_  				=      end[divergence_idx]
										return tuple(
										    path + (slice(__UpperCamelCase    ,edi + 1	),) + s
										    for s in _get_minimal_slice_set(
										        [0 for _ in start[divergence_idx + 1 :]]    ,end[divergence_idx + 1 :]    ,dims[divergence_idx + 1 :]    ,start_edges=[True for _ in start_edges[divergence_idx + 1 :]]    ,end_edges=end_edges[divergence_idx + 1 :]    ,)	)

					# If both start and end are at the edges of the subtree rooted at
					# divergence_idx, we can just select the whole subtree at once
					if start_edges[divergence_idx] and end_edges[divergence_idx]:
										slices.append(path + (slice(start[divergence_idx]    ,end[divergence_idx] + 1	),)	)
					# If just start is at the edge, we can grab almost all of the subtree,
					# treating only the ragged bottom edge as an edge case
					elif start_edges[divergence_idx]:
										slices.append(path + (slice(start[divergence_idx]    ,end[divergence_idx]	),)	)
										slices.extend(lower()	)
					# Analogous to the previous case, but the top is ragged this time
					elif end_edges[divergence_idx]:
										slices.extend(upper()	)
										slices.append(path + (slice(start[divergence_idx] + 1    ,end[divergence_idx] + 1	),)	)
					# If both sides of the range are ragged, we need to handle both sides
					# separately. If there's contiguous meat in between them, we can index it
					# in one big chunk
					else:
										slices.extend(upper()	)
										lowerCamelCase_  				=      end[divergence_idx] - start[divergence_idx]
										if middle_ground > 1:
															slices.append(path + (slice(start[divergence_idx] + 1    ,end[divergence_idx]	),)	)
										slices.extend(lower()	)

					return slices







@torch.jit.ignore
def   _UpperCamelCase	(		__UpperCamelCase    ,__UpperCamelCase    ,__UpperCamelCase    ,__UpperCamelCase	)       ->			torch.Tensor:
					lowerCamelCase_  				=      t.shape[:no_batch_dims]
					lowerCamelCase_  				=      list(_flat_idx_to_idx(__UpperCamelCase    ,__UpperCamelCase	)	)
					# _get_minimal_slice_set is inclusive
					lowerCamelCase_  				=      list(_flat_idx_to_idx(flat_end - 1    ,__UpperCamelCase	)	)

					# Get an ordered list of slices to perform
					lowerCamelCase_  				=      _get_minimal_slice_set(
					    __UpperCamelCase    ,__UpperCamelCase    ,__UpperCamelCase    ,)

					lowerCamelCase_  				=      [t[s] for s in slices]

					return torch.cat([s.view((-1,) + t.shape[no_batch_dims:]	) for s in sliced_tensors]	)







def   _UpperCamelCase	(		__UpperCamelCase    ,__UpperCamelCase    ,__UpperCamelCase    ,__UpperCamelCase    ,__UpperCamelCase = False    ,__UpperCamelCase = None    ,__UpperCamelCase = False    ,)       ->			Any:
					if not (len(__UpperCamelCase	) > 0):
										raise ValueError('Must provide at least one input'	)

					lowerCamelCase_  				=      [shape[:no_batch_dims] for shape in _fetch_dims(__UpperCamelCase	)]
					lowerCamelCase_  				=      tuple([max(__UpperCamelCase	) for s in zip(*__UpperCamelCase	)]	)

					def _prep_inputs(__UpperCamelCase	) -> torch.Tensor:
										if not low_mem:
															if not sum(t.shape[:no_batch_dims]	) == no_batch_dims:
																				lowerCamelCase_  				=      t.expand(orig_batch_dims + t.shape[no_batch_dims:]	)
															lowerCamelCase_  				=      t.reshape(-1    ,*t.shape[no_batch_dims:]	)
										else:
															lowerCamelCase_  				=      t.expand(orig_batch_dims + t.shape[no_batch_dims:]	)
										return t

					lowerCamelCase_  				=      tensor_tree_map(_prep_inputs    ,__UpperCamelCase	)
					lowerCamelCase_  				=      None
					if _out is not None:
										lowerCamelCase_  				=      tensor_tree_map(lambda __UpperCamelCase	: t.view([-1] + list(t.shape[no_batch_dims:]	)	)    ,_out	)

					lowerCamelCase_  				=      1
					for d in orig_batch_dims:
										flat_batch_dim *= d

					lowerCamelCase_  				=      flat_batch_dim // chunk_size + (flat_batch_dim % chunk_size != 0)

					def _select_chunk(__UpperCamelCase	) -> torch.Tensor:
										return t[i : i + chunk_size] if t.shape[0] != 1 else t

					lowerCamelCase_  				=      0
					lowerCamelCase_  				=      prepped_outputs
					for _ in range(__UpperCamelCase	):
										# Chunk the input
										if not low_mem:
															lowerCamelCase_  				=      _select_chunk
										else:
															lowerCamelCase_  				=      partial(
															    _chunk_slice    ,flat_start=__UpperCamelCase    ,flat_end=min(__UpperCamelCase    ,i + chunk_size	)    ,no_batch_dims=len(__UpperCamelCase	)    ,)

										lowerCamelCase_  				=      tensor_tree_map(__UpperCamelCase    ,__UpperCamelCase	)

										# Run the layer on the chunk
										lowerCamelCase_  				=      layer(**__UpperCamelCase	)

										# Allocate space for the output
										if out is None:
															lowerCamelCase_  				=      tensor_tree_map(lambda __UpperCamelCase	: t.new_zeros((flat_batch_dim,) + t.shape[1:]	)    ,__UpperCamelCase	)

										# Put the chunk in its pre-allocated space
										if isinstance(__UpperCamelCase    ,__UpperCamelCase	):

															def assign(__UpperCamelCase    ,__UpperCamelCase	) -> None:
																				for k, v in da.items():
																									if isinstance(__UpperCamelCase    ,__UpperCamelCase	):
																														assign(__UpperCamelCase    ,da[k]	)
																									else:
																														if _add_into_out:
																																			v[i : i + chunk_size] += da[k]
																														else:
																																			lowerCamelCase_  				=      da[k]

															assign(__UpperCamelCase    ,__UpperCamelCase	)
										elif isinstance(__UpperCamelCase    ,__UpperCamelCase	):
															for xa, xa in zip(__UpperCamelCase    ,__UpperCamelCase	):
																				if _add_into_out:
																									xa[i : i + chunk_size] += xa
																				else:
																									lowerCamelCase_  				=      xa
										elif isinstance(__UpperCamelCase    ,torch.Tensor	):
															if _add_into_out:
																				out[i : i + chunk_size] += output_chunk
															else:
																				lowerCamelCase_  				=      output_chunk
										else:
															raise ValueError('Not supported'	)

										i += chunk_size

					lowerCamelCase_  				=      tensor_tree_map(lambda __UpperCamelCase	: t.view(orig_batch_dims + t.shape[1:]	)    ,__UpperCamelCase	)

					return out







class  UpperCAmelCase :

		'''simple docstring'''






		def __init__(					self   ,			SCREAMING_SNAKE_CASE_ = 512   ,			)  ->     int:






							'''simple docstring'''



							lowerCamelCase_  				=      max_chunk_size
							lowerCamelCase_  				=      None
							lowerCamelCase_  				=      None
		def 			UpperCamelCase(					self   ,			SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_		)  ->     int:






							'''simple docstring'''



							logging.info('Tuning chunk size...'		)

							if min_chunk_size >= self.max_chunk_size:
												return min_chunk_size

							lowerCamelCase_  				=      [2**l for l in range(int(math.log(self.max_chunk_size   ,			2		)		) + 1		)]
							lowerCamelCase_  				=      [c for c in candidates if c > min_chunk_size]
							lowerCamelCase_  				=      [min_chunk_size] + candidates
							candidates[-1] += 4

							def test_chunk_size(SCREAMING_SNAKE_CASE_		) -> bool:
												try:
																	with torch.no_grad():
																						fn(*SCREAMING_SNAKE_CASE_   ,			chunk_size=SCREAMING_SNAKE_CASE_		)
																	return True
												except RuntimeError:
																	return False

							lowerCamelCase_  				=      0
							lowerCamelCase_  				=      len(SCREAMING_SNAKE_CASE_		) - 1
							while i > min_viable_chunk_size_index:
												lowerCamelCase_  				=      test_chunk_size(candidates[i]		)
												if not viable:
																	lowerCamelCase_  				=      (min_viable_chunk_size_index + i) // 2
												else:
																	lowerCamelCase_  				=      i
																	lowerCamelCase_  				=      (i + len(SCREAMING_SNAKE_CASE_		) - 1) // 2

							return candidates[min_viable_chunk_size_index]
		def 			UpperCamelCase(					self   ,			SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_		)  ->     bool:






							'''simple docstring'''



							lowerCamelCase_  				=      True
							for aa, aa in zip(SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_		):
												assert type(SCREAMING_SNAKE_CASE_		) == type(SCREAMING_SNAKE_CASE_		)
												if isinstance(SCREAMING_SNAKE_CASE_   ,			(list, tuple)		):
																	consistent &= self._compare_arg_caches(SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_		)
												elif isinstance(SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_		):
																	lowerCamelCase_  				=      [v for _, v in sorted(aa.items()   ,			key=lambda SCREAMING_SNAKE_CASE_		: x[0]		)]
																	lowerCamelCase_  				=      [v for _, v in sorted(aa.items()   ,			key=lambda SCREAMING_SNAKE_CASE_		: x[0]		)]
																	consistent &= self._compare_arg_caches(SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_		)
												else:
																	consistent &= aa == aa

							return consistent






		def 			UpperCamelCase(					self   ,			SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_   ,			)  ->     int:






							'''simple docstring'''



							lowerCamelCase_  				=      True
							lowerCamelCase_  				=      tree_map(lambda SCREAMING_SNAKE_CASE_		: a.shape if isinstance(SCREAMING_SNAKE_CASE_   ,			torch.Tensor		) else a   ,			SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_		)
							if self.cached_arg_data is not None:
												# If args have changed shape/value, we need to re-tune
												assert len(self.cached_arg_data		) == len(SCREAMING_SNAKE_CASE_		)
												lowerCamelCase_  				=      self._compare_arg_caches(self.cached_arg_data   ,			SCREAMING_SNAKE_CASE_		)
							else:
												# Otherwise, we can reuse the precomputed value
												lowerCamelCase_  				=      False

							if not consistent:
												lowerCamelCase_  				=      self._determine_favorable_chunk_size(
												    SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_   ,			SCREAMING_SNAKE_CASE_   ,			)
												lowerCamelCase_  				=      arg_data

							assert self.cached_chunk_size is not None

							return self.cached_chunk_size





def   __lowerCAmelCase    (				UpperCAmelCase__					:   int							)	->     int:

							if not isinstance(UpperCAmelCase__      ,					UpperCAmelCase__							):
														raise ValueError("""multiplicative_persistence() only accepts integral values"""							)
							if num < 0:
														raise ValueError("""multiplicative_persistence() does not accept negative values"""							)

							lowerCamelCase_					=       0
							lowerCamelCase_					=       str(UpperCAmelCase__							)

							while len(UpperCAmelCase__							) != 1:
														lowerCamelCase_					=       [int(UpperCAmelCase__							) for i in num_string]

														lowerCamelCase_					=       1
														for i in range(0      ,					len(UpperCAmelCase__							)							):
																					total *= numbers[i]

														lowerCamelCase_					=       str(UpperCAmelCase__							)

														steps += 1
							return steps



def   __lowerCAmelCase    (				UpperCAmelCase__					:   int							)	->     int:

							if not isinstance(UpperCAmelCase__      ,					UpperCAmelCase__							):
														raise ValueError("""additive_persistence() only accepts integral values"""							)
							if num < 0:
														raise ValueError("""additive_persistence() does not accept negative values"""							)

							lowerCamelCase_					=       0
							lowerCamelCase_					=       str(UpperCAmelCase__							)

							while len(UpperCAmelCase__							) != 1:
														lowerCamelCase_					=       [int(UpperCAmelCase__							) for i in num_string]

														lowerCamelCase_					=       0
														for i in range(0      ,					len(UpperCAmelCase__							)							):
																					total += numbers[i]

														lowerCamelCase_					=       str(UpperCAmelCase__							)

														steps += 1
							return steps


if __name__ == "__main__":
		import doctest

		doctest.testmod()





