



"""simple docstring"""


import re

from flax.core.frozen_dict import freeze
from flax.traverse_util import flatten_dict, unflatten_dict
from jax.experimental import PartitionSpec as P


# Sentinels
__A   :							List[str]										=   object()

# For specifying empty leaf dict `{}`
__A   :							List[str]										=   object()







def  lowercase	(      _SCREAMING_SNAKE_CASE   :						Union[str, Any]					,     _SCREAMING_SNAKE_CASE   :						Union[str, Any]				):






				'''simple docstring'''



				_UpperCAmelCase					=    tuple((re.compile(x + '''$'''				) for x in qs)				)
				for i in range(len(_SCREAMING_SNAKE_CASE				) - len(_SCREAMING_SNAKE_CASE				) + 1				):
								_UpperCAmelCase					=    [x.match(_SCREAMING_SNAKE_CASE				) for x, y in zip(_SCREAMING_SNAKE_CASE					,     ks[i:]				)]
								if matches and all(_SCREAMING_SNAKE_CASE				):
												return True
				return False







def  lowercase	(      _SCREAMING_SNAKE_CASE   :						Union[str, Any]				):






				'''simple docstring'''



				def replace(_SCREAMING_SNAKE_CASE   :						Union[str, Any]					,     _SCREAMING_SNAKE_CASE   :						Union[str, Any]				):
								for rule, replacement in rules:
												if _match(_SCREAMING_SNAKE_CASE					,     _SCREAMING_SNAKE_CASE				):
																return replacement
								return val

				return replace







def  lowercase	(      ):






				'''simple docstring'''



				return [
				    # embeddings
				    (("transformer", "wpe", "embedding"), P('''mp'''					,     _SCREAMING_SNAKE_CASE				)),
				    (("transformer", "wte", "embedding"), P('''mp'''					,     _SCREAMING_SNAKE_CASE				)),
				    # atention
				    (("attention", "(q_proj|k_proj|v_proj)", "kernel"), P(_SCREAMING_SNAKE_CASE					,     '''mp'''				)),
				    (("attention", "out_proj", "kernel"), P('''mp'''					,     _SCREAMING_SNAKE_CASE				)),
				    (("attention", "out_proj", "bias"), None),
				    # mlp
				    (("mlp", "c_fc", "kernel"), P(_SCREAMING_SNAKE_CASE					,     '''mp'''				)),
				    (("mlp", "c_fc", "bias"), P('''mp'''				)),
				    (("mlp", "c_proj", "kernel"), P('''mp'''					,     _SCREAMING_SNAKE_CASE				)),
				    (("mlp", "c_proj", "bias"), None),
				    # layer norms
				    ((r"ln_\d+", "bias"), None),
				    ((r"\d+", r"ln_\d+", "scale"), None),
				    (("ln_f", "bias"), None),
				    (("ln_f", "scale"), None),
				]







def  lowercase	(      _SCREAMING_SNAKE_CASE   :						Tuple				):






				'''simple docstring'''



				_UpperCAmelCase					=    _get_partition_rules()
				_UpperCAmelCase					=    _replacement_rules(_SCREAMING_SNAKE_CASE				)
				_UpperCAmelCase					=    {k: _unmatched for k in flatten_dict(_SCREAMING_SNAKE_CASE				)}
				_UpperCAmelCase					=    {k: replace(_SCREAMING_SNAKE_CASE					,     _SCREAMING_SNAKE_CASE				) for k, v in initd.items()}
				assert _unmatched not in result.values(), "Incomplete partition spec."
				return freeze(unflatten_dict(_SCREAMING_SNAKE_CASE				)				)








"""simple docstring"""


import operator







def  lowercase	(      _SCREAMING_SNAKE_CASE   :						list					,     _SCREAMING_SNAKE_CASE   :						bool = False					,     _SCREAMING_SNAKE_CASE   :						list | None = None				):






				'''simple docstring'''



				_UpperCAmelCase					=    operator.lt if reverse else operator.gt
				_UpperCAmelCase					=    solution or []

				if not arr:
								return solution

				_UpperCAmelCase					=    [arr.pop(0				)]
				for i, item in enumerate(_SCREAMING_SNAKE_CASE				):
								if _operator(_SCREAMING_SNAKE_CASE					,     sublist[-1]				):
												sublist.append(_SCREAMING_SNAKE_CASE				)
												arr.pop(_SCREAMING_SNAKE_CASE				)

    #  merging sublist into solution list
				if not solution:
								solution.extend(_SCREAMING_SNAKE_CASE				)
				else:
								while sublist:
												_UpperCAmelCase					=    sublist.pop(0				)
												for i, xx in enumerate(_SCREAMING_SNAKE_CASE				):
																if not _operator(_SCREAMING_SNAKE_CASE					,     _SCREAMING_SNAKE_CASE				):
																				solution.insert(_SCREAMING_SNAKE_CASE					,     _SCREAMING_SNAKE_CASE				)
																				break
												else:
																solution.append(_SCREAMING_SNAKE_CASE				)

				strand_sort(_SCREAMING_SNAKE_CASE					,     _SCREAMING_SNAKE_CASE					,     _SCREAMING_SNAKE_CASE				)
				return solution


if __name__ == "__main__":
					assert strand_sort([4, 3, 5, 1, 2]) == [1, 2, 3, 4, 5]
					assert strand_sort([4, 3, 5, 1, 2], reverse=True) == [5, 4, 3, 2, 1]



