




"""simple docstring"""




import inspect
import os

import torch
from transformers import AutoModel
from transformers.testing_utils import mockenv_context
from transformers.trainer_utils import set_seed

import accelerate
from accelerate.accelerator import Accelerator
from accelerate.state import AcceleratorState
from accelerate.test_utils.testing import (
    AccelerateTestCase,
    TempDirTestCase,
    execute_subprocess_async,
    require_cuda,
    require_fsdp,
    require_multi_gpu,
    slow,
)
from accelerate.utils.constants import (
    FSDP_AUTO_WRAP_POLICY,
    FSDP_BACKWARD_PREFETCH,
    FSDP_SHARDING_STRATEGY,
    FSDP_STATE_DICT_TYPE,
)
from accelerate.utils.dataclasses import FullyShardedDataParallelPlugin
from accelerate.utils.other import patch_environment


set_seed(42)

_lowerCamelCase     :		Tuple								=       """bert-base-cased"""
_lowerCamelCase     :		Any								=       """fp16"""
_lowerCamelCase     :		Union[str, Any]								=       """bf16"""
_lowerCamelCase     :		List[str]								=       [FPaa, BFaa]


@require_fsdp
@require_cuda
class     UpperCamelCase_   (			__UpperCamelCase					):

    '''simple docstring'''






    def 	SCREAMING_SNAKE_CASE							(      self				:     Tuple)						->List[str]:





           '''simple docstring'''

           super().setUp()

           A__							=   dict(
               ACCELERATE_USE_FSDP='''true''' ,			MASTER_ADDR='''localhost''' ,			MASTER_PORT='''10999''' ,			RANK='''0''' ,			LOCAL_RANK='''0''' ,			WORLD_SIZE='''1''' ,			)


    def 	SCREAMING_SNAKE_CASE							(      self				:     Optional[int])						->List[Any]:





           '''simple docstring'''

           from torch.distributed.fsdp.fully_sharded_data_parallel import ShardingStrategy

           for i, strategy in enumerate(_lowerCAmelCase):
                  A__							=   self.dist_env.copy()
                  A__							=   f"""{i + 1}"""
                  A__							=   strategy
                  with mockenv_context(**_lowerCAmelCase):
                         A__							=   FullyShardedDataParallelPlugin()
                         self.assertEqual(fsdp_plugin.sharding_strategy ,			ShardingStrategy(i + 1))


    def 	SCREAMING_SNAKE_CASE							(      self				:     Union[str, Any])						->int:





           '''simple docstring'''

           from torch.distributed.fsdp.fully_sharded_data_parallel import BackwardPrefetch

           for i, prefetch_policy in enumerate(_lowerCAmelCase):
                  A__							=   self.dist_env.copy()
                  A__							=   prefetch_policy
                  with mockenv_context(**_lowerCAmelCase):
                         A__							=   FullyShardedDataParallelPlugin()
                         if prefetch_policy == "NO_PREFETCH":
                                self.assertIsNone(fsdp_plugin.backward_prefetch)
                         else:
                                self.assertEqual(fsdp_plugin.backward_prefetch ,			BackwardPrefetch(i + 1))


    def 	SCREAMING_SNAKE_CASE							(      self				:     str)						->Optional[int]:





           '''simple docstring'''

           from torch.distributed.fsdp.fully_sharded_data_parallel import StateDictType

           for i, state_dict_type in enumerate(_lowerCAmelCase):
                  A__							=   self.dist_env.copy()
                  A__							=   state_dict_type
                  with mockenv_context(**_lowerCAmelCase):
                         A__							=   FullyShardedDataParallelPlugin()
                         self.assertEqual(fsdp_plugin.state_dict_type ,			StateDictType(i + 1))
                         if state_dict_type == "FULL_STATE_DICT":
                                self.assertTrue(fsdp_plugin.state_dict_config.offload_to_cpu)
                                self.assertTrue(fsdp_plugin.state_dict_config.ranka_only)


    def 	SCREAMING_SNAKE_CASE							(      self				:     List[Any])						->int:





           '''simple docstring'''

           A__							=   AutoModel.from_pretrained(_lowerCAmelCase)
           for policy in FSDP_AUTO_WRAP_POLICY:
                  A__							=   self.dist_env.copy()
                  A__							=   policy
                  if policy == "TRANSFORMER_BASED_WRAP":
                         A__							=   """BertLayer"""
                  elif policy == "SIZE_BASED_WRAP":
                         A__							=   """2000"""
                  with mockenv_context(**_lowerCAmelCase):
                         A__							=   FullyShardedDataParallelPlugin()
                         fsdp_plugin.set_auto_wrap_policy(_lowerCAmelCase)
                         if policy == "NO_WRAP":
                                self.assertIsNone(fsdp_plugin.auto_wrap_policy)
                         else:
                                self.assertIsNotNone(fsdp_plugin.auto_wrap_policy)

           A__							=   self.dist_env.copy()
           A__							=   """TRANSFORMER_BASED_WRAP"""
           A__							=   """T5Layer"""
           with mockenv_context(**_lowerCAmelCase):
                  A__							=   FullyShardedDataParallelPlugin()
                  with self.assertRaises(_lowerCAmelCase) as cm:
                         fsdp_plugin.set_auto_wrap_policy(_lowerCAmelCase)
                  self.assertTrue('''Could not find the transformer layer class to wrap in the model.''' in str(cm.exception))

           A__							=   self.dist_env.copy()
           A__							=   """SIZE_BASED_WRAP"""
           A__							=   """0"""
           with mockenv_context(**_lowerCAmelCase):
                  A__							=   FullyShardedDataParallelPlugin()
                  fsdp_plugin.set_auto_wrap_policy(_lowerCAmelCase)
                  self.assertIsNone(fsdp_plugin.auto_wrap_policy)


    def 	SCREAMING_SNAKE_CASE							(      self				:     Union[str, Any])						->Any:





           '''simple docstring'''

           from torch.distributed.fsdp.fully_sharded_data_parallel import MixedPrecision
           from torch.distributed.fsdp.sharded_grad_scaler import ShardedGradScaler

           for mp_dtype in dtypes:
                  A__							=   self.dist_env.copy()
                  A__							=   mp_dtype
                  with mockenv_context(**_lowerCAmelCase):
                         A__							=   Accelerator()
                         if mp_dtype == "fp16":
                                A__							=   torch.floataa
                         elif mp_dtype == "bf16":
                                A__							=   torch.bfloataa
                         A__							=   MixedPrecision(param_dtype=_lowerCAmelCase ,			reduce_dtype=_lowerCAmelCase ,			buffer_dtype=_lowerCAmelCase)
                         self.assertEqual(accelerator.state.fsdp_plugin.mixed_precision_policy ,			_lowerCAmelCase)
                         if mp_dtype == FPaa:
                                self.assertTrue(isinstance(accelerator.scaler ,			_lowerCAmelCase))
                         elif mp_dtype == BFaa:
                                self.assertIsNone(accelerator.scaler)
                         AcceleratorState._reset_state(_lowerCAmelCase)





    def 	SCREAMING_SNAKE_CASE							(      self				:     Optional[int])						->Dict:





           '''simple docstring'''

           from torch.distributed.fsdp.fully_sharded_data_parallel import CPUOffload

           for flag in [True, False]:
                  A__							=   self.dist_env.copy()
                  A__							=   str(_lowerCAmelCase).lower()
                  with mockenv_context(**_lowerCAmelCase):
                         A__							=   FullyShardedDataParallelPlugin()
                         self.assertEqual(fsdp_plugin.cpu_offload ,			CPUOffload(offload_params=_lowerCAmelCase))


@require_fsdp
@require_multi_gpu
@slow
class     UpperCamelCase_   (			__UpperCamelCase					):

    '''simple docstring'''






    def 	SCREAMING_SNAKE_CASE							(      self				:     Tuple)						->str:





           '''simple docstring'''

           super().setUp()
           A__							=   0.82
           A__							=   [
               """fsdp_shard_grad_op_transformer_based_wrap""",
               """fsdp_full_shard_transformer_based_wrap""",
           ]
           A__							=   {
               """multi_gpu_fp16""": 3_200,
               """fsdp_shard_grad_op_transformer_based_wrap_fp16""": 2_000,
               """fsdp_full_shard_transformer_based_wrap_fp16""": 1_900,
               # Disabling below test as it overwhelms the RAM memory usage
               # on CI self-hosted runner leading to tests getting killed.
               # "fsdp_full_shard_cpu_offload_transformer_based_wrap_fp32": 1500,  # fp16 was leading to indefinite hang
           }
           A__							=   160
           A__							=   160

           A__							=   inspect.getfile(accelerate.test_utils)
           A__							=   os.path.sep.join(mod_file.split(os.path.sep)[:-1] + ['''scripts''', '''external_deps'''])


    def 	SCREAMING_SNAKE_CASE							(      self				:     List[str])						->Tuple:





           '''simple docstring'''

           A__							=   os.path.join(self.test_scripts_folder ,			'''test_performance.py''')
           A__							=   ["""accelerate""", """launch""", """--num_processes=2""", """--num_machines=1""", """--machine_rank=0""", """--use_fsdp"""]
           for config in self.performance_configs:
                  A__							=   cmd.copy()
                  for i, strategy in enumerate(_lowerCAmelCase):
                         if strategy.lower() in config:
                                cmd_config.append(f"""--fsdp_sharding_strategy={i+1}""")
                                break

                  if "fp32" in config:
                         cmd_config.append('''--mixed_precision=no''')
                  else:
                         cmd_config.append('''--mixed_precision=fp16''')

                  if "cpu_offload" in config:
                         cmd_config.append('''--fsdp_offload_params=True''')

                  for policy in FSDP_AUTO_WRAP_POLICY:
                         if policy.lower() in config:
                                cmd_config.append(f"""--fsdp_auto_wrap_policy={policy}""")
                                break

                  if policy == "TRANSFORMER_BASED_WRAP":
                         cmd_config.append('''--fsdp_transformer_layer_cls_to_wrap=BertLayer''')
                  elif policy == "SIZE_BASED_WRAP":
                         cmd_config.append('''--fsdp_min_num_params=2000''')

                  cmd_config.extend(
                      [
                          self.test_file_path,
                          f"""--output_dir={self.tmpdir}""",
                          f"""--performance_lower_bound={self.performance_lower_bound}""",
                      ])
                  with patch_environment(omp_num_threads=1):
                         execute_subprocess_async(_lowerCAmelCase ,			env=os.environ.copy())


    def 	SCREAMING_SNAKE_CASE							(      self				:     Optional[Any])						->List[Any]:





           '''simple docstring'''

           A__							=   os.path.join(self.test_scripts_folder ,			'''test_checkpointing.py''')
           A__							=   [
               """accelerate""",
               """launch""",
               """--num_processes=2""",
               """--num_machines=1""",
               """--machine_rank=0""",
               """--use_fsdp""",
               """--mixed_precision=fp16""",
               """--fsdp_transformer_layer_cls_to_wrap=BertLayer""",
           ]

           for i, strategy in enumerate(_lowerCAmelCase):
                  A__							=   cmd.copy()
                  cmd_config.append(f"""--fsdp_sharding_strategy={i+1}""")
                  if strategy != "FULL_SHARD":
                         continue
                  A__							=   len(_lowerCAmelCase)
                  for state_dict_type in FSDP_STATE_DICT_TYPE:
                         A__							=   cmd_config[:state_dict_config_index]
                         cmd_config.append(f"""--fsdp_state_dict_type={state_dict_type}""")
                         cmd_config.extend(
                             [
                                 self.test_file_path,
                                 f"""--output_dir={self.tmpdir}""",
                                 '''--partial_train_epoch=1''',
                             ])
                         with patch_environment(omp_num_threads=1):
                                execute_subprocess_async(_lowerCAmelCase ,			env=os.environ.copy())

                         A__							=   cmd_config[:-1]
                         A__							=   os.path.join(self.tmpdir ,			'''epoch_0''')
                         cmd_config.extend(
                             [
                                 f"""--resume_from_checkpoint={resume_from_checkpoint}""",
                             ])
                         with patch_environment(omp_num_threads=1):
                                execute_subprocess_async(_lowerCAmelCase ,			env=os.environ.copy())





    def 	SCREAMING_SNAKE_CASE							(      self				:     Any)						->Tuple:





           '''simple docstring'''

           A__							=   os.path.join(self.test_scripts_folder ,			'''test_peak_memory_usage.py''')
           A__							=   [
               """accelerate""",
               """launch""",
               """--num_processes=2""",
               """--num_machines=1""",
               """--machine_rank=0""",
           ]
           for spec, peak_mem_upper_bound in self.peak_memory_usage_upper_bound.items():
                  A__							=   cmd.copy()
                  if "fp16" in spec:
                         cmd_config.extend(['''--mixed_precision=fp16'''])
                  else:
                         cmd_config.extend(['''--mixed_precision=no'''])

                  if "multi_gpu" in spec:
                         continue
                  else:
                         cmd_config.extend(['''--use_fsdp'''])
                         for i, strategy in enumerate(_lowerCAmelCase):
                                if strategy.lower() in spec:
                                       cmd_config.append(f"""--fsdp_sharding_strategy={i+1}""")
                                       break

                         if "cpu_offload" in spec:
                                cmd_config.append('''--fsdp_offload_params=True''')

                         for policy in FSDP_AUTO_WRAP_POLICY:
                                if policy.lower() in spec:
                                       cmd_config.append(f"""--fsdp_auto_wrap_policy={policy}""")
                                       break

                         if policy == "TRANSFORMER_BASED_WRAP":
                                cmd_config.append('''--fsdp_transformer_layer_cls_to_wrap=BertLayer''')
                         elif policy == "SIZE_BASED_WRAP":
                                cmd_config.append('''--fsdp_min_num_params=2000''')

                  cmd_config.extend(
                      [
                          self.test_file_path,
                          f"""--output_dir={self.tmpdir}""",
                          f"""--peak_memory_upper_bound={peak_mem_upper_bound}""",
                          f"""--n_train={self.n_train}""",
                          f"""--n_val={self.n_val}""",
                      ])
                  with patch_environment(omp_num_threads=1):
                         execute_subprocess_async(_lowerCAmelCase ,			env=os.environ.copy())








from __future__ import annotations

import queue


class     UpperCamelCase_   :

    '''simple docstring'''






    def __init__(      self				:     Optional[Any] ,			UpperCAmelCase__				:     Dict)						->Any:





           '''simple docstring'''

           A__							=   data
           A__							=   None
           A__							=   None







def SCREAMING_SNAKE_CASE    (	)       ->	TreeNode:



       """simple docstring"""

       print('''\n********Press N to stop entering at any point of time********\n'''						)
       A__							=   input('''Enter the value of the root node: '''						).strip().lower()
       A__							=   queue.Queue()
       A__							=   TreeNode(int(lowercase_						)						)
       q.put(lowercase_						)
       while not q.empty():
              A__							=   q.get()
              A__							=   f"""Enter the left node of {node_found.data}: """
              A__							=   input(lowercase_						).strip().lower() or '''n'''
              if check == "n":
                     return tree_node
              A__							=   TreeNode(int(lowercase_						)						)
              A__							=   left_node
              q.put(lowercase_						)
              A__							=   f"""Enter the right node of {node_found.data}: """
              A__							=   input(lowercase_						).strip().lower() or '''n'''
              if check == "n":
                     return tree_node
              A__							=   TreeNode(int(lowercase_						)						)
              A__							=   right_node
              q.put(lowercase_						)
       raise







def SCREAMING_SNAKE_CASE    (	lowercase_						)       ->	None:



       """simple docstring"""

       if not isinstance(lowercase_			,    lowercase_						) or not node:
              return
       print(node.data			,    end=''','''						)
       pre_order(node.left						)
       pre_order(node.right						)







def SCREAMING_SNAKE_CASE    (	lowercase_						)       ->	None:



       """simple docstring"""

       if not isinstance(lowercase_			,    lowercase_						) or not node:
              return
       in_order(node.left						)
       print(node.data			,    end=''','''						)
       in_order(node.right						)







def SCREAMING_SNAKE_CASE    (	lowercase_						)       ->	None:



       """simple docstring"""

       if not isinstance(lowercase_			,    lowercase_						) or not node:
              return
       post_order(node.left						)
       post_order(node.right						)
       print(node.data			,    end=''','''						)







def SCREAMING_SNAKE_CASE    (	lowercase_						)       ->	None:



       """simple docstring"""

       if not isinstance(lowercase_			,    lowercase_						) or not node:
              return
       A__							=   queue.Queue()
       q.put(lowercase_						)
       while not q.empty():
              A__							=   q.get()
              print(node_dequeued.data			,    end=''','''						)
              if node_dequeued.left:
                     q.put(node_dequeued.left						)
              if node_dequeued.right:
                     q.put(node_dequeued.right						)







def SCREAMING_SNAKE_CASE    (	lowercase_						)       ->	None:



       """simple docstring"""

       if not isinstance(lowercase_			,    lowercase_						) or not node:
              return
       A__							=   queue.Queue()
       q.put(lowercase_						)
       while not q.empty():
              A__							=   []
              while not q.empty():
                     A__							=   q.get()
                     print(node_dequeued.data			,    end=''','''						)
                     if node_dequeued.left:
                            list_.append(node_dequeued.left						)
                     if node_dequeued.right:
                            list_.append(node_dequeued.right						)
              print()
              for node in list_:
                     q.put(lowercase_						)







def SCREAMING_SNAKE_CASE    (	lowercase_						)       ->	None:



       """simple docstring"""

       if not isinstance(lowercase_			,    lowercase_						) or not node:
              return
       A__							=   []
       A__							=   node
       while n or stack:
              while n:  # start from root node, find its left child
                     print(n.data			,    end=''','''						)
                     stack.append(lowercase_						)
                     A__							=   n.left
              # end of while means current node doesn't have left child
              A__							=   stack.pop()
              # start to traverse its right child
              A__							=   n.right







def SCREAMING_SNAKE_CASE    (	lowercase_						)       ->	None:



       """simple docstring"""

       if not isinstance(lowercase_			,    lowercase_						) or not node:
              return
       A__							=   []
       A__							=   node
       while n or stack:
              while n:
                     stack.append(lowercase_						)
                     A__							=   n.left
              A__							=   stack.pop()
              print(n.data			,    end=''','''						)
              A__							=   n.right







def SCREAMING_SNAKE_CASE    (	lowercase_						)       ->	None:



       """simple docstring"""

       if not isinstance(lowercase_			,    lowercase_						) or not node:
              return
       A__			,							A__							=   [], []
       A__							=   node
       stacka.append(lowercase_						)
       while stacka:  # to find the reversed order of post order, store it in stack2
              A__							=   stacka.pop()
              if n.left:
                     stacka.append(n.left						)
              if n.right:
                     stacka.append(n.right						)
              stacka.append(lowercase_						)
       while stacka:  # pop up from stack2 will be the post order
              print(stacka.pop().data			,    end=''','''						)







def SCREAMING_SNAKE_CASE    (	lowercase_ = ""			,    lowercase_=50			,    lowercase_="*"						)       ->	str:



       """simple docstring"""

       if not s:
              return "\n" + width * char
       A__			,							A__							=   divmod(width - len(lowercase_						) - 2			,    2						)
       return f"""{left * char} {s} {(left + extra) * char}"""


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  print(prompt("""Binary Tree Traversals"""))

  _lowerCamelCase     :		TreeNode								=       build_tree()
  print(prompt("""Pre Order Traversal"""))
  pre_order(node)
  print(prompt() + """\n""")

  print(prompt("""In Order Traversal"""))
  in_order(node)
  print(prompt() + """\n""")

  print(prompt("""Post Order Traversal"""))
  post_order(node)
  print(prompt() + """\n""")

  print(prompt("""Level Order Traversal"""))
  level_order(node)
  print(prompt() + """\n""")

  print(prompt("""Actual Level Order Traversal"""))
  level_order_actual(node)
  print("""*""" * 50 + """\n""")

  print(prompt("""Pre Order Traversal - Iteration Version"""))
  pre_order_iter(node)
  print(prompt() + """\n""")

  print(prompt("""In Order Traversal - Iteration Version"""))
  in_order_iter(node)
  print(prompt() + """\n""")

  print(prompt("""Post Order Traversal - Iteration Version"""))
  post_order_iter(node)
  print(prompt())


