





"""simple docstring"""





from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
SCREAMING_SNAKE_CASE__					=   0

SCREAMING_SNAKE_CASE__					=   [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

SCREAMING_SNAKE_CASE__					=   [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

SCREAMING_SNAKE_CASE__					=   tuple[int, int]

class 		lowercase					:





      def __init__(       self      ,						lowercase      ,						lowercase      ,						lowercase      ,						lowercase      ,						lowercase      ,						lowercase      ,						)		->     None:
            lowerCAmelCase  						=       pos_x
            lowerCAmelCase  						=       pos_y
            lowerCAmelCase  						=       (pos_y, pos_x)
            lowerCAmelCase  						=       goal_x
            lowerCAmelCase  						=       goal_y
            lowerCAmelCase  						=       g_cost
            lowerCAmelCase  						=       parent
            lowerCAmelCase  						=       self.calculate_heuristic()
            lowerCAmelCase  						=       self.g_cost + self.h_cost





      def     _snake_case			(       self )		->     float:
            lowerCAmelCase  						=       self.pos_x - self.goal_x
            lowerCAmelCase  						=       self.pos_y - self.goal_y
            if HEURISTIC == 1:
                  return abs(lowercase ) + abs(lowercase )
            else:
                  return sqrt(dy**2 + dx**2 )





      def __lt__(       self      ,						lowercase )		->     bool:
            return self.f_cost < other.f_cost







class 		lowercase					:





      def __init__(       self      ,						lowercase      ,						lowercase )		->     List[Any]:
            lowerCAmelCase  						=       Node(start[1]      ,						start[0]      ,						goal[1]      ,						goal[0]      ,						0      ,						lowercase )
            lowerCAmelCase  						=       Node(goal[1]      ,						goal[0]      ,						goal[1]      ,						goal[0]      ,						99_999      ,						lowercase )

            lowerCAmelCase  						=       [self.start]
            lowerCAmelCase  						=       []

            lowerCAmelCase  						=       False





      def     _snake_case			(       self )		->     list[TPosition]:
            while self.open_nodes:
                  # Open Nodes are sorted using __lt__
                  self.open_nodes.sort()
                  lowerCAmelCase  						=       self.open_nodes.pop(0 )

                  if current_node.pos == self.target.pos:
                        return self.retrace_path(lowercase )

                  self.closed_nodes.append(lowercase )
                  lowerCAmelCase  						=       self.get_successors(lowercase )

                  for child_node in successors:
                        if child_node in self.closed_nodes:
                              continue

                        if child_node not in self.open_nodes:
                              self.open_nodes.append(lowercase )
                        else:
                              # retrieve the best current path
                              lowerCAmelCase  						=       self.open_nodes.pop(self.open_nodes.index(lowercase ) )

                              if child_node.g_cost < better_node.g_cost:
                                    self.open_nodes.append(lowercase )
                              else:
                                    self.open_nodes.append(lowercase )

            return [self.start.pos]





      def     _snake_case			(       self      ,						lowercase )		->     list[Node]:
            lowerCAmelCase  						=       []
            for action in delta:
                  lowerCAmelCase  						=       parent.pos_x + action[1]
                  lowerCAmelCase  						=       parent.pos_y + action[0]
                  if not (0 <= pos_x <= len(grid[0] ) - 1 and 0 <= pos_y <= len(lowercase ) - 1):
                        continue

                  if grid[pos_y][pos_x] != 0:
                        continue

                  successors.append(
                      Node(
                          lowercase      ,						lowercase      ,						self.target.pos_y      ,						self.target.pos_x      ,						parent.g_cost + 1      ,						lowercase      ,						) )
            return successors





      def     _snake_case			(       self      ,						lowercase )		->     list[TPosition]:
            lowerCAmelCase  						=       node
            lowerCAmelCase  						=       []
            while current_node is not None:
                  path.append((current_node.pos_y, current_node.pos_x) )
                  lowerCAmelCase  						=       current_node.parent
            path.reverse()
            return path







class 		lowercase					:





      def __init__(       self      ,						lowercase      ,						lowercase )		->     None:
            lowerCAmelCase  						=       AStar(lowercase      ,						lowercase )
            lowerCAmelCase  						=       AStar(lowercase      ,						lowercase )
            lowerCAmelCase  						=       False





      def     _snake_case			(       self )		->     list[TPosition]:
            while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
                  self.fwd_astar.open_nodes.sort()
                  self.bwd_astar.open_nodes.sort()
                  lowerCAmelCase  						=       self.fwd_astar.open_nodes.pop(0 )
                  lowerCAmelCase  						=       self.bwd_astar.open_nodes.pop(0 )

                  if current_bwd_node.pos == current_fwd_node.pos:
                        return self.retrace_bidirectional_path(
                            lowercase      ,						lowercase )

                  self.fwd_astar.closed_nodes.append(lowercase )
                  self.bwd_astar.closed_nodes.append(lowercase )

                  lowerCAmelCase  						=       current_bwd_node
                  lowerCAmelCase  						=       current_fwd_node

                  lowerCAmelCase  						=       {
                      self.fwd_astar: self.fwd_astar.get_successors(lowercase ),
                      self.bwd_astar: self.bwd_astar.get_successors(lowercase ),
                  }

                  for astar in [self.fwd_astar, self.bwd_astar]:
                        for child_node in successors[astar]:
                              if child_node in astar.closed_nodes:
                                    continue

                              if child_node not in astar.open_nodes:
                                    astar.open_nodes.append(lowercase )
                              else:
                                    # retrieve the best current path
                                    lowerCAmelCase  						=       astar.open_nodes.pop(
                                        astar.open_nodes.index(lowercase ) )

                                    if child_node.g_cost < better_node.g_cost:
                                          astar.open_nodes.append(lowercase )
                                    else:
                                          astar.open_nodes.append(lowercase )

            return [self.fwd_astar.start.pos]





      def     _snake_case			(       self      ,						lowercase      ,						lowercase )		->     list[TPosition]:
            lowerCAmelCase  						=       self.fwd_astar.retrace_path(lowercase )
            lowerCAmelCase  						=       self.bwd_astar.retrace_path(lowercase )
            bwd_path.pop()
            bwd_path.reverse()
            lowerCAmelCase  						=       fwd_path + bwd_path
            return path


if __name__ == "__main__":
       # all coordinates are given in format [y,x]
       SCREAMING_SNAKE_CASE__					=   (0, 0)
       SCREAMING_SNAKE_CASE__					=   (len(grid) - 1, len(grid[0]) - 1)
       for elem in grid:
              print(elem)

       SCREAMING_SNAKE_CASE__					=   time.time()
       SCREAMING_SNAKE_CASE__					=   AStar(init, goal)
       SCREAMING_SNAKE_CASE__					=   a_star.search()
       SCREAMING_SNAKE_CASE__					=   time.time() - start_time
       print(f'AStar execution time = {end_time:f} seconds')

       SCREAMING_SNAKE_CASE__					=   time.time()
       SCREAMING_SNAKE_CASE__					=   BidirectionalAStar(init, goal)
       SCREAMING_SNAKE_CASE__					=   time.time() - bd_start_time
       print(f'BidirectionalAStar execution time = {bd_end_time:f} seconds')








from __future__ import annotations

import math
import random
from typing import Any



class 		UpperCamelCase__  :
   def __init__(self :					Optional[Any]   ):
    __a :  list[Any]						=  []
    __a :  int						=  0
    __a :  int						=  0
   def       lowerCAmelCase			(self :					Optional[int]   ):
    return self.head == self.tail
   def       lowerCAmelCase			(self :					List[Any]					,				snake_case_ :					Any   ):
    self.data.append(snake_case_   )
    __a :  str						=  self.tail + 1
   def       lowerCAmelCase			(self :					Optional[int]   ):
    __a :  int						=  self.data[self.head]
    __a :  Union[str, Any]						=  self.head + 1
    return ret
   def       lowerCAmelCase			(self :					Union[str, Any]   ):
    return self.tail - self.head







   def       lowerCAmelCase			(self :					Union[str, Any]   ):
    print(self.data   )
    print('''**************'''   )
    print(self.data[self.head : self.tail]   )





class 		UpperCamelCase__  :
   def __init__(self :					List[str]					,				snake_case_ :					Any   ):
    __a :  List[str]						=  data
    __a :  MyNode | None						=  None
    __a :  MyNode | None						=  None
    __a :  int						=  1
   def       lowerCAmelCase			(self :					int   ):
    return self.data
   def       lowerCAmelCase			(self :					Dict   ):
    return self.left
   def       lowerCAmelCase			(self :					int   ):
    return self.right
   def       lowerCAmelCase			(self :					int   ):
    return self.height
   def       lowerCAmelCase			(self :					Optional[Any]					,				snake_case_ :					Any   ):
    __a :  Tuple						=  data
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					MyNode | None   ):
    __a :  Any						=  node
   def       lowerCAmelCase			(self :					Union[str, Any]					,				snake_case_ :					MyNode | None   ):
    __a :  List[str]						=  node







   def       lowerCAmelCase			(self :					Optional[int]					,				snake_case_ :					int   ):
    __a :  Union[str, Any]						=  height





def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode | None  ):
 if node is None:
  return 0
 return node.get_height()




def    __UpperCamelCase     (				lowerCAmelCase__							:				int  ,   lowerCAmelCase__							:				int  ):
 if a > b:
  return a
 return b




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 print('''left rotation node:'''  ,   node.get_data()  )
 __a :  str						=  node.get_left()
 assert ret is not None
 node.set_left(ret.get_right()  )
 ret.set_right(lowerCAmelCase__  )
 __a :  List[Any]						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 __a :  Union[str, Any]						=  my_max(get_height(ret.get_right()  )  ,   get_height(ret.get_left()  )  ) + 1
 ret.set_height(lowerCAmelCase__  )
 return ret




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 print('''right rotation node:'''  ,   node.get_data()  )
 __a :  List[Any]						=  node.get_right()
 assert ret is not None
 node.set_right(ret.get_left()  )
 ret.set_left(lowerCAmelCase__  )
 __a :  Union[str, Any]						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 __a :  List[str]						=  my_max(get_height(ret.get_right()  )  ,   get_height(ret.get_left()  )  ) + 1
 ret.set_height(lowerCAmelCase__  )
 return ret




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 __a :  Union[str, Any]						=  node.get_left()
 assert left_child is not None
 node.set_left(left_rotation(lowerCAmelCase__  )  )
 return right_rotation(lowerCAmelCase__  )




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 __a :  Optional[int]						=  node.get_right()
 assert right_child is not None
 node.set_right(right_rotation(lowerCAmelCase__  )  )
 return left_rotation(lowerCAmelCase__  )




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode | None  ,   lowerCAmelCase__							:				Any  ):
 if node is None:
  return MyNode(lowerCAmelCase__  )
 if data < node.get_data():
  node.set_left(insert_node(node.get_left()  ,   lowerCAmelCase__  )  )
  if (
      get_height(node.get_left()  ) - get_height(node.get_right()  ) == 2
  ):  # an unbalance detected
   __a :  Tuple						=  node.get_left()
   assert left_child is not None
   if (
       data < left_child.get_data()
   ):  # new node is the left child of the left child
    __a :  str						=  right_rotation(lowerCAmelCase__  )
   else:
    __a :  Dict						=  lr_rotation(lowerCAmelCase__  )
 else:
  node.set_right(insert_node(node.get_right()  ,   lowerCAmelCase__  )  )
  if get_height(node.get_right()  ) - get_height(node.get_left()  ) == 2:
   __a :  Dict						=  node.get_right()
   assert right_child is not None
   if data < right_child.get_data():
    __a :  str						=  rl_rotation(lowerCAmelCase__  )
   else:
    __a :  Tuple						=  left_rotation(lowerCAmelCase__  )
 __a :  Any						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 return node




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 while True:
  __a :  Union[str, Any]						=  root.get_right()
  if right_child is None:
   break
  __a :  str						=  right_child
 return root.get_data()




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 while True:
  __a :  Optional[int]						=  root.get_left()
  if left_child is None:
   break
  __a :  int						=  left_child
 return root.get_data()




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ,   lowerCAmelCase__							:				Any  ):
 __a :  Optional[Any]						=  root.get_left()
 __a :  List[str]						=  root.get_right()
 if root.get_data() == data:
  if left_child is not None and right_child is not None:
   __a :  str						=  get_left_most(lowerCAmelCase__  )
   root.set_data(lowerCAmelCase__  )
   root.set_right(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )
  elif left_child is not None:
   __a :  int						=  left_child
  elif right_child is not None:
   __a :  List[Any]						=  right_child
  else:
   return None
 elif root.get_data() > data:
  if left_child is None:
   print('''No such data'''  )
   return root
  else:
   root.set_left(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )
 else:  # root.get_data() < data
  if right_child is None:
   return root
  else:
   root.set_right(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )

 if get_height(lowerCAmelCase__  ) - get_height(lowerCAmelCase__  ) == 2:
  assert right_child is not None
  if get_height(right_child.get_right()  ) > get_height(right_child.get_left()  ):
   __a :  List[Any]						=  left_rotation(lowerCAmelCase__  )
  else:
   __a :  Union[str, Any]						=  rl_rotation(lowerCAmelCase__  )
 elif get_height(lowerCAmelCase__  ) - get_height(lowerCAmelCase__  ) == -2:
  assert left_child is not None
  if get_height(left_child.get_left()  ) > get_height(left_child.get_right()  ):
   __a :  int						=  right_rotation(lowerCAmelCase__  )
  else:
   __a :  Tuple						=  lr_rotation(lowerCAmelCase__  )
 __a :  str						=  my_max(get_height(root.get_right()  )  ,   get_height(root.get_left()  )  ) + 1
 root.set_height(lowerCAmelCase__  )
 return root



class 		UpperCamelCase__  :
   def __init__(self :					Optional[Any]   ):
    __a :  MyNode | None						=  None
   def       lowerCAmelCase			(self :					List[Any]   ):
    return get_height(self.root   )
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					Any   ):
    print('''insert:''' + str(snake_case_   )   )
    __a :  List[Any]						=  insert_node(self.root					,				snake_case_   )
   def       lowerCAmelCase			(self :					Dict					,				snake_case_ :					Any   ):
    print('''delete:''' + str(snake_case_   )   )
    if self.root is None:
     print('''Tree is empty!'''   )
     return
    __a :  Union[str, Any]						=  del_node(self.root					,				snake_case_   )







   def __str__(self :					List[str]					,				):  # a level traversale, gives a more intuitive look on the tree
    __a :  Union[str, Any]						=  ''''''
    __a :  int						=  MyQueue()
    q.push(self.root   )
    __a :  List[str]						=  self.get_height()
    if layer == 0:
     return output
    __a :  List[Any]						=  0
    while not q.is_empty():
     __a :  List[str]						=  q.pop()
     __a :  Optional[int]						=  ''' ''' * int(math.pow(2					,				layer - 1   )   )
     output += space
     if node is None:
      output += "*"
      q.push(snake_case_   )
      q.push(snake_case_   )
     else:
      output += str(node.get_data()   )
      q.push(node.get_left()   )
      q.push(node.get_right()   )
     output += space
     __a :  int						=  cnt + 1
     for i in range(1_0_0   ):
      if cnt == math.pow(2					,				snake_case_   ) - 1:
       __a :  str						=  layer - 1
       if layer == 0:
        output += "\n*************************************"
        return output
       output += "\n"
       break
    output += "\n*************************************"
    return output





def    __UpperCamelCase     (				):
 import doctest

 doctest.testmod()


if __name__ == "__main__":
      _test()
      lowercase__       =AVLtree()
      lowercase__       =list(range(10))
      random.shuffle(lst)
      for i in lst:
            t.insert(i)
            print(str(t))
      random.shuffle(lst)
      for i in lst:
            t.del_node(i)
            print(str(t))
