





import collections
import os
import re
from pathlib import Path


UpperCAmelCase_      							=     """src/transformers"""


# Matches is_xxx_available()
UpperCAmelCase_      							=     re.compile(R"""is\_([a-z_]*)_available()""")
# Catches a one-line _import_struct = {xxx}
UpperCAmelCase_      							=     re.compile(R"""^_import_structure\s+=\s+\{([^\}]+)\}""")
# Catches a line with a key-values pattern: "bla": ["foo", "bar"]
UpperCAmelCase_      							=     re.compile(R"""\s+\"\S*\":\s+\[([^\]]*)\]""")
# Catches a line if not is_foo_available
UpperCAmelCase_      							=     re.compile(R"""^\s*if\s+not\s+is\_[a-z_]*\_available\(\)""")
# Catches a line _import_struct["bla"].append("foo")
UpperCAmelCase_      							=     re.compile(R"""^\s*_import_structure\[\"\S*\"\]\.append\(\"(\S*)\"\)""")
# Catches a line _import_struct["bla"].extend(["foo", "bar"]) or _import_struct["bla"] = ["foo", "bar"]
UpperCAmelCase_      							=     re.compile(R"""^\s*_import_structure\[\S*\](?:\.extend\(|\s*=\s+)\[([^\]]*)\]""")
# Catches a line with an object between quotes and a comma:     "MyModel",
UpperCAmelCase_      							=     re.compile(R"""^\s+\"([^\"]+)\",""")
# Catches a line with objects between brackets only:    ["foo", "bar"],
UpperCAmelCase_      							=     re.compile(R"""^\s+\[([^\]]+)\]""")
# Catches a line with from foo import bar, bla, boo
UpperCAmelCase_      							=     re.compile(R"""\s+from\s+\S*\s+import\s+([^\(\s].*)\n""")
# Catches a line with try:
UpperCAmelCase_      							=     re.compile(R"""^\s*try:""")
# Catches a line with else:
UpperCAmelCase_      							=     re.compile(R"""^\s*else:""")





def 						lowerCamelCase__     (     UpperCamelCase__			:       int						)			-> Tuple:



					'''simple docstring'''




					if _re_test_backend.search(UpperCamelCase__						) is None:
										return None
					_snake_case									=				[b[0] for b in _re_backend.findall(UpperCamelCase__						)]
					backends.sort()
					return "_and_".join(UpperCamelCase__						)





def 						lowerCamelCase__     (     UpperCamelCase__			:       str						)			-> Optional[Any]:



					'''simple docstring'''




					with open(UpperCamelCase__       ,    'r'       ,    encoding='utf-8'       ,    newline='\n'						) as f:
										_snake_case									=				f.readlines()

					_snake_case									=				0
					while line_index < len(UpperCamelCase__						) and not lines[line_index].startswith('_import_structure = {'						):
										line_index += 1

					# If this is a traditional init, just return.
					if line_index >= len(UpperCamelCase__						):
										return None

					# First grab the objects without a specific backend in _import_structure
					_snake_case									=				[]
					while not lines[line_index].startswith('if TYPE_CHECKING'						) and find_backend(lines[line_index]						) is None:
										_snake_case									=				lines[line_index]
										# If we have everything on a single line, let's deal with it.
										if _re_one_line_import_struct.search(UpperCamelCase__						):
															_snake_case									=				_re_one_line_import_struct.search(UpperCamelCase__						).groups()[0]
															_snake_case									=				re.findall(R'\[([^\]]+)\]'       ,    UpperCamelCase__						)
															for imp in imports:
																				objects.extend([obj[1:-1] for obj in imp.split(', '						)]						)
															line_index += 1
															continue
										_snake_case									=				_re_import_struct_key_value.search(UpperCamelCase__						)
										if single_line_import_search is not None:
															_snake_case									=				[obj[1:-1] for obj in single_line_import_search.groups()[0].split(', '						) if len(UpperCamelCase__						) > 0]
															objects.extend(UpperCamelCase__						)
										elif line.startswith(' ' * 8 + '"'						):
															objects.append(line[9:-3]						)
										line_index += 1

					_snake_case									=				{'none': objects}
					# Let's continue with backend-specific objects in _import_structure
					while not lines[line_index].startswith('if TYPE_CHECKING'						):
										# If the line is an if not is_backend_available, we grab all objects associated.
										_snake_case									=				find_backend(lines[line_index]						)
										# Check if the backend declaration is inside a try block:
										if _re_try.search(lines[line_index - 1]						) is None:
															_snake_case									=				None

										if backend is not None:
															line_index += 1

															# Scroll until we hit the else block of try-except-else
															while _re_else.search(lines[line_index]						) is None:
																				line_index += 1

															line_index += 1

															_snake_case									=				[]
															# Until we unindent, add backend objects to the list
															while len(lines[line_index]						) <= 1 or lines[line_index].startswith(' ' * 4						):
																				_snake_case									=				lines[line_index]
																				if _re_import_struct_add_one.search(UpperCamelCase__						) is not None:
																									objects.append(_re_import_struct_add_one.search(UpperCamelCase__						).groups()[0]						)
																				elif _re_import_struct_add_many.search(UpperCamelCase__						) is not None:
																									_snake_case									=				_re_import_struct_add_many.search(UpperCamelCase__						).groups()[0].split(', '						)
																									_snake_case									=				[obj[1:-1] for obj in imports if len(UpperCamelCase__						) > 0]
																									objects.extend(UpperCamelCase__						)
																				elif _re_between_brackets.search(UpperCamelCase__						) is not None:
																									_snake_case									=				_re_between_brackets.search(UpperCamelCase__						).groups()[0].split(', '						)
																									_snake_case									=				[obj[1:-1] for obj in imports if len(UpperCamelCase__						) > 0]
																									objects.extend(UpperCamelCase__						)
																				elif _re_quote_object.search(UpperCamelCase__						) is not None:
																									objects.append(_re_quote_object.search(UpperCamelCase__						).groups()[0]						)
																				elif line.startswith(' ' * 8 + '"'						):
																									objects.append(line[9:-3]						)
																				elif line.startswith(' ' * 12 + '"'						):
																									objects.append(line[13:-3]						)
																				line_index += 1

															_snake_case									=				objects
										else:
															line_index += 1

    # At this stage we are in the TYPE_CHECKING part, first grab the objects without a specific backend
					_snake_case									=				[]
					while (
					    line_index < len(UpperCamelCase__						)
					    and find_backend(lines[line_index]						) is None
					    and not lines[line_index].startswith('else'						)
					):
										_snake_case									=				lines[line_index]
										_snake_case									=				_re_import.search(UpperCamelCase__						)
										if single_line_import_search is not None:
															objects.extend(single_line_import_search.groups()[0].split(', '						)						)
										elif line.startswith(' ' * 8						):
															objects.append(line[8:-2]						)
										line_index += 1

					_snake_case									=				{'none': objects}
					# Let's continue with backend-specific objects
					while line_index < len(UpperCamelCase__						):
										# If the line is an if is_backend_available, we grab all objects associated.
										_snake_case									=				find_backend(lines[line_index]						)
										# Check if the backend declaration is inside a try block:
										if _re_try.search(lines[line_index - 1]						) is None:
															_snake_case									=				None

										if backend is not None:
															line_index += 1

															# Scroll until we hit the else block of try-except-else
															while _re_else.search(lines[line_index]						) is None:
																				line_index += 1

															line_index += 1

															_snake_case									=				[]
															# Until we unindent, add backend objects to the list
															while len(lines[line_index]						) <= 1 or lines[line_index].startswith(' ' * 8						):
																				_snake_case									=				lines[line_index]
																				_snake_case									=				_re_import.search(UpperCamelCase__						)
																				if single_line_import_search is not None:
																									objects.extend(single_line_import_search.groups()[0].split(', '						)						)
																				elif line.startswith(' ' * 12						):
																									objects.append(line[12:-2]						)
																				line_index += 1

															_snake_case									=				objects
										else:
															line_index += 1

					return import_dict_objects, type_hint_objects





def 						lowerCamelCase__     (     UpperCamelCase__			:       str       ,    UpperCamelCase__			:       Dict						)			-> Tuple:



					'''simple docstring'''




					def find_duplicates(UpperCamelCase__			:       Dict						):
										return [k for k, v in collections.Counter(UpperCamelCase__						).items() if v > 1]

					if list(import_dict_objects.keys()						) != list(type_hint_objects.keys()						):
										return ["Both sides of the init do not have the same backends!"]

					_snake_case									=				[]
					for key in import_dict_objects.keys():
										_snake_case									=				find_duplicates(import_dict_objects[key]						)
										if duplicate_imports:
															errors.append(F'''Duplicate _import_structure definitions for: {duplicate_imports}'''						)
										_snake_case									=				find_duplicates(type_hint_objects[key]						)
										if duplicate_type_hints:
															errors.append(F'''Duplicate TYPE_CHECKING objects for: {duplicate_type_hints}'''						)

										if sorted(set(import_dict_objects[key]						)						) != sorted(set(type_hint_objects[key]						)						):
															_snake_case									=				'base imports' if key == 'none' else F'''{key} backend'''
															errors.append(F'''Differences for {name}:'''						)
															for a in type_hint_objects[key]:
																				if a not in import_dict_objects[key]:
																									errors.append(F'''  {a} in TYPE_HINT but not in _import_structure.'''						)
															for a in import_dict_objects[key]:
																				if a not in type_hint_objects[key]:
																									errors.append(F'''  {a} in _import_structure but not in TYPE_HINT.'''						)
					return errors





def 						lowerCamelCase__     (     )			-> List[Any]:



					'''simple docstring'''




					_snake_case									=				[]
					for root, _, files in os.walk(UpperCamelCase__						):
										if "__init__.py" in files:
															_snake_case									=				os.path.join(UpperCamelCase__       ,    '__init__.py'						)
															_snake_case									=				parse_init(UpperCamelCase__						)
															if objects is not None:
																				_snake_case									=				analyze_results(*UpperCamelCase__						)
																				if len(UpperCamelCase__						) > 0:
																									_snake_case									=				F'''Problem in {fname}, both halves do not define the same objects.\n{errors[0]}'''
																									failures.append('\n'.join(UpperCamelCase__						)						)
					if len(UpperCamelCase__						) > 0:
										raise ValueError('\n\n'.join(UpperCamelCase__						)						)





def 						lowerCamelCase__     (     )			-> List[Any]:



					'''simple docstring'''




					_snake_case									=				[]
					for path, directories, files in os.walk(UpperCamelCase__						):
										for folder in directories:
															# Ignore private modules
															if folder.startswith('_'						):
																				directories.remove(UpperCamelCase__						)
																				continue
															# Ignore leftovers from branches (empty folders apart from pycache)
															if len(list((Path(UpperCamelCase__						) / folder).glob('*.py'						)						)						) == 0:
																				continue
															_snake_case									=				str((Path(UpperCamelCase__						) / folder).relative_to(UpperCamelCase__						)						)
															_snake_case									=				short_path.replace(os.path.sep       ,    '.'						)
															submodules.append(UpperCamelCase__						)
										for fname in files:
															if fname == "__init__.py":
																				continue
															_snake_case									=				str((Path(UpperCamelCase__						) / fname).relative_to(UpperCamelCase__						)						)
															_snake_case									=				short_path.replace('.py'       ,    ''						).replace(os.path.sep       ,    '.'						)
															if len(submodule.split('.'						)						) == 1:
																				submodules.append(UpperCamelCase__						)
					return submodules


UpperCAmelCase_      							=     [
    """convert_pytorch_checkpoint_to_tf2""",
    """modeling_flax_pytorch_utils""",
    """models.esm.openfold_utils""",
]





def 						lowerCamelCase__     (     )			-> Optional[int]:



					'''simple docstring'''




					from transformers.utils import direct_transformers_import

					_snake_case									=				direct_transformers_import(UpperCamelCase__						)

					_snake_case									=				set(transformers._import_structure.keys()						)
					# This contains all the base keys of the _import_structure object defined in the init, but if the user is missing
					# some optional dependencies, they may not have all of them. Thus we read the init to read all additions and
					# (potentiall re-) add them.
					with open(os.path.join(UpperCamelCase__       ,    '__init__.py'						)       ,    'r'						) as f:
										_snake_case									=				f.read()
					import_structure_keys.update(set(re.findall(R'import_structure\[\"([^\"]*)\"\]'       ,    UpperCamelCase__						)						)						)

					_snake_case									=				[
					    module
					    for module in get_transformers_submodules()
					    if module not in IGNORE_SUBMODULES and module not in import_structure_keys
					]

					if len(UpperCamelCase__						) > 0:
										_snake_case									=				'\n'.join(F'''- {module}''' for module in module_not_registered						)
										raise ValueError(
										    'The following submodules are not properly registed in the main init of Transformers:\n'
										    F'''{list_of_modules}\n'''
										    'Make sure they appear somewhere in the keys of `_import_structure` with an empty list as value.'						)


if __name__ == "__main__":
					check_all_inits()
					check_submodules()










def 						lowerCamelCase__     (     UpperCamelCase__			:       list						)			-> list:



					'''simple docstring'''




					_snake_case									=				len(UpperCamelCase__						)
					for i in range(1       ,    UpperCamelCase__						):
										_snake_case									=				collection[i]
										_snake_case									=				0
										_snake_case									=				i - 1

										while low <= high:
															_snake_case									=				(low + high) // 2
															if val < collection[mid]:
																				_snake_case									=				mid - 1
															else:
																				_snake_case									=				mid + 1
										for j in range(UpperCamelCase__       ,    UpperCamelCase__       ,    -1						):
															_snake_case									=				collection[j - 1]
										_snake_case									=				val
					return collection


if __name__ == "__main__":
					UpperCAmelCase_      							=     input("""Enter numbers separated by a comma:\n""").strip()
					UpperCAmelCase_      							=     [int(item) for item in user_input.split(""",""")]
					print(binary_insertion_sort(unsorted))



