






import tensorflow as tf

from ...tf_utils import shape_list


class 					_snake_case						(			tf.keras.layers.Layer ):






	def __init__(		self					,UpperCamelCase					,UpperCamelCase					,UpperCamelCase					,UpperCamelCase					,UpperCamelCase=1					,UpperCamelCase=False					,**UpperCamelCase       )						->    Any:
					super().__init__(**UpperCamelCase       )

					snake_case__      :List[Any]         =   vocab_size
					snake_case__      :Any         =   d_embed
					snake_case__      :Tuple         =   d_proj

					snake_case__      :Any         =   cutoffs + [vocab_size]
					snake_case__      :str         =   [0] + self.cutoffs
					snake_case__      :str         =   div_val

					snake_case__      :Dict         =   self.cutoffs[0]
					snake_case__      :Tuple         =   len(self.cutoffs       ) - 1
					snake_case__      :int         =   self.shortlist_size + self.n_clusters
					snake_case__      :List[str]         =   keep_order

					snake_case__      :List[Any]         =   []
					snake_case__      :Any         =   []






	def    lowerCAmelCase_							(		self					,UpperCamelCase       )						->    List[str]:
					if self.n_clusters > 0:
									snake_case__      :int         =   self.add_weight(
									    shape=(self.n_clusters, self.d_embed)					,initializer="zeros"					,trainable=UpperCamelCase					,name="cluster_weight"       )
									snake_case__      :str         =   self.add_weight(
									    shape=(self.n_clusters,)					,initializer="zeros"					,trainable=UpperCamelCase					,name="cluster_bias"       )

					if self.div_val == 1:
									for i in range(len(self.cutoffs       )       ):
													if self.d_proj != self.d_embed:
																	snake_case__      :Optional[int]         =   self.add_weight(
																	    shape=(self.d_embed, self.d_proj)					,initializer="zeros"					,trainable=UpperCamelCase					,name=f'out_projs_._{i}'					,)
																	self.out_projs.append(UpperCamelCase       )
													else:
																	self.out_projs.append(UpperCamelCase       )
													snake_case__      :str         =   self.add_weight(
													    shape=(self.vocab_size, self.d_embed)					,initializer="zeros"					,trainable=UpperCamelCase					,name=f'out_layers_._{i}_._weight'					,)
													snake_case__      :Tuple         =   self.add_weight(
													    shape=(self.vocab_size,)					,initializer="zeros"					,trainable=UpperCamelCase					,name=f'out_layers_._{i}_._bias'					,)
													self.out_layers.append((weight, bias)       )
					else:
									for i in range(len(self.cutoffs       )       ):
													snake_case__    ,						snake_case__      :List[str]         =   self.cutoff_ends[i], self.cutoff_ends[i + 1]
													snake_case__      :Optional[Any]         =   self.d_embed // (self.div_val**i)

													snake_case__      :List[str]         =   self.add_weight(
													    shape=(d_emb_i, self.d_proj)					,initializer="zeros"					,trainable=UpperCamelCase					,name=f'out_projs_._{i}'       )
													self.out_projs.append(UpperCamelCase       )
													snake_case__      :List[Any]         =   self.add_weight(
													    shape=(r_idx - l_idx, d_emb_i)					,initializer="zeros"					,trainable=UpperCamelCase					,name=f'out_layers_._{i}_._weight'					,)
													snake_case__      :List[Any]         =   self.add_weight(
													    shape=(r_idx - l_idx,)					,initializer="zeros"					,trainable=UpperCamelCase					,name=f'out_layers_._{i}_._bias'					,)
													self.out_layers.append((weight, bias)       )
					super().build(UpperCamelCase       )






	@staticmethod
	def    lowerCAmelCase_							(		UpperCamelCase					,UpperCamelCase					,UpperCamelCase					,UpperCamelCase=None       )						->    str:
					snake_case__      :Any         =   x
					if proj is not None:
									snake_case__      :List[Any]         =   tf.einsum("ibd,ed->ibe"					,UpperCamelCase					,UpperCamelCase       )
					return tf.einsum("ibd,nd->ibn"					,UpperCamelCase					,UpperCamelCase       ) + b






	@staticmethod
	def    lowerCAmelCase_							(		UpperCamelCase					,UpperCamelCase       )						->    Optional[Any]:
					snake_case__      :int         =   shape_list(UpperCamelCase       )
					snake_case__      :Union[str, Any]         =   tf.range(lp_size[0]					,dtype=target.dtype       )
					snake_case__      :Tuple         =   tf.stack([r, target]					,1       )
					return tf.gather_nd(UpperCamelCase					,UpperCamelCase       )






	def    lowerCAmelCase_							(		self					,UpperCamelCase					,UpperCamelCase					,UpperCamelCase=True					,UpperCamelCase=False       )						->    str:
					snake_case__      :int         =   0
					if self.n_clusters == 0:
									snake_case__      :List[str]         =   self._logit(UpperCamelCase					,self.out_layers[0][0]					,self.out_layers[0][1]					,self.out_projs[0]       )
									if target is not None:
													snake_case__      :Union[str, Any]         =   tf.nn.sparse_softmax_cross_entropy_with_logits(labels=UpperCamelCase					,logits=UpperCamelCase       )
									snake_case__      :int         =   tf.nn.log_softmax(UpperCamelCase					,axis=-1       )
					else:
									snake_case__      :Optional[int]         =   shape_list(UpperCamelCase       )
									snake_case__      :str         =   []
									snake_case__      :int         =   tf.zeros(hidden_sizes[:2]       )
									for i in range(len(self.cutoffs       )       ):
													snake_case__    ,						snake_case__      :List[Any]         =   self.cutoff_ends[i], self.cutoff_ends[i + 1]
													if target is not None:
																	snake_case__      :Optional[int]         =   (target >= l_idx) & (target < r_idx)
																	snake_case__      :Any         =   tf.where(UpperCamelCase       )
																	snake_case__      :List[Any]         =   tf.boolean_mask(UpperCamelCase					,UpperCamelCase       ) - l_idx

													if self.div_val == 1:
																	snake_case__      :Union[str, Any]         =   self.out_layers[0][0][l_idx:r_idx]
																	snake_case__      :int         =   self.out_layers[0][1][l_idx:r_idx]
													else:
																	snake_case__      :int         =   self.out_layers[i][0]
																	snake_case__      :str         =   self.out_layers[i][1]

													if i == 0:
																	snake_case__      :Optional[int]         =   tf.concat([cur_W, self.cluster_weight]					,0       )
																	snake_case__      :Union[str, Any]         =   tf.concat([cur_b, self.cluster_bias]					,0       )

																	snake_case__      :Optional[Any]         =   self._logit(UpperCamelCase					,UpperCamelCase					,UpperCamelCase					,self.out_projs[0]       )
																	snake_case__      :Optional[Any]         =   tf.nn.log_softmax(UpperCamelCase       )
																	out.append(head_logprob[..., : self.cutoffs[0]]       )
																	if target is not None:
																					snake_case__      :int         =   tf.boolean_mask(UpperCamelCase					,UpperCamelCase       )
																					snake_case__      :Optional[Any]         =   self._gather_logprob(UpperCamelCase					,UpperCamelCase       )
													else:
																	snake_case__      :Any         =   self._logit(UpperCamelCase					,UpperCamelCase					,UpperCamelCase					,self.out_projs[i]       )
																	snake_case__      :Union[str, Any]         =   tf.nn.log_softmax(UpperCamelCase       )
																	snake_case__      :str         =   self.cutoffs[0] + i - 1  # No probability for the head cluster
																	snake_case__      :Dict         =   head_logprob[..., cluster_prob_idx, None] + tail_logprob
																	out.append(UpperCamelCase       )
																	if target is not None:
																					snake_case__      :Union[str, Any]         =   tf.boolean_mask(UpperCamelCase					,UpperCamelCase       )
																					snake_case__      :Any         =   tf.boolean_mask(UpperCamelCase					,UpperCamelCase       )
																					snake_case__      :str         =   self._gather_logprob(UpperCamelCase					,UpperCamelCase       )
																					cur_logprob += cur_head_logprob[:, self.cutoff_ends[1] + i - 1]
													if target is not None:
																	loss += tf.scatter_nd(UpperCamelCase					,-cur_logprob					,shape_list(UpperCamelCase       )       )
									snake_case__      :List[str]         =   tf.concat(UpperCamelCase					,axis=-1       )

					if target is not None:
									if return_mean:
													snake_case__      :int         =   tf.reduce_mean(UpperCamelCase       )
									# Add the training-time loss value to the layer using `self.add_loss()`.
									self.add_loss(UpperCamelCase       )

									# Log the loss as a metric (we could log arbitrary metrics,
									# including different metrics for training and inference.
									self.add_metric(UpperCamelCase					,name=self.name					,aggregation="mean" if return_mean else ""       )

					return out







def 					lowercase_ (    __snake_case     :							list      )     -> list:





				'''simple docstring'''


				if any(not isinstance(__snake_case	,	__snake_case      ) or x < 0 for x in sequence      ):
								raise TypeError("Sequence must be list of non-negative integers"      )
				for _ in range(len(__snake_case      )      ):
								for i, (rod_upper, rod_lower) in enumerate(zip(__snake_case	,	sequence[1:]      )      ):
												if rod_upper > rod_lower:
																sequence[i] -= rod_upper - rod_lower
																sequence[i + 1] += rod_upper - rod_lower
				return sequence


if __name__ == "__main__":
	assert bead_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
	assert bead_sort([7, 9, 4, 3, 5]) == [3, 4, 5, 7, 9]