

'''simple docstring'''







from __future__ import annotations

import math
import random
from typing import Any


class    A__ :



    def __init__(   self    )  -> None:





           '''simple docstring'''
           A_		   = []
           A_		   = 0
           A_		   = 0



    def    snake_case_     (   self    )  -> bool:





           '''simple docstring'''
           return self.head == self.tail



    def    snake_case_     (   self						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           self.data.append(UpperCamelCase__    )
           A_		   = self.tail + 1



    def    snake_case_     (   self    )  -> Any:





           '''simple docstring'''
           A_		   = self.data[self.head]
           A_		   = self.head + 1
           return ret



    def    snake_case_     (   self    )  -> int:





           '''simple docstring'''
           return self.tail - self.head







    def    snake_case_     (   self    )  -> None:





           '''simple docstring'''
           print(self.data    )
           print("""**************"""    )
           print(self.data[self.head : self.tail]    )


class    A__ :



    def __init__(   self						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           A_		   = data
           A_		   = None
           A_		   = None
           A_		   = 1



    def    snake_case_     (   self    )  -> Any:





           '''simple docstring'''
           return self.data



    def    snake_case_     (   self    )  -> MyNode | None:





           '''simple docstring'''
           return self.left



    def    snake_case_     (   self    )  -> MyNode | None:





           '''simple docstring'''
           return self.right



    def    snake_case_     (   self    )  -> int:





           '''simple docstring'''
           return self.height



    def    snake_case_     (   self						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           A_		   = data



    def    snake_case_     (   self						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           A_		   = node



    def    snake_case_     (   self						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           A_		   = node







    def    snake_case_     (   self						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           A_		   = height

def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     int:
       if node is None:
              return 0
       return node.get_height()
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__			)     ->     int:
       if a > b:
              return a
       return b
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     MyNode:
       print("""left rotation node:""",    node.get_data()			)
       A_		   = node.get_left()
       assert ret is not None
       node.set_left(ret.get_right()			)
       ret.set_right(UpperCAmelCase__			)
       A_		   = my_max(get_height(node.get_right()			),    get_height(node.get_left()			)			) + 1
       node.set_height(UpperCAmelCase__			)
       A_		   = my_max(get_height(ret.get_right()			),    get_height(ret.get_left()			)			) + 1
       ret.set_height(UpperCAmelCase__			)
       return ret
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     MyNode:
       print("""right rotation node:""",    node.get_data()			)
       A_		   = node.get_right()
       assert ret is not None
       node.set_right(ret.get_left()			)
       ret.set_left(UpperCAmelCase__			)
       A_		   = my_max(get_height(node.get_right()			),    get_height(node.get_left()			)			) + 1
       node.set_height(UpperCAmelCase__			)
       A_		   = my_max(get_height(ret.get_right()			),    get_height(ret.get_left()			)			) + 1
       ret.set_height(UpperCAmelCase__			)
       return ret
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     MyNode:
       A_		   = node.get_left()
       assert left_child is not None
       node.set_left(left_rotation(UpperCAmelCase__			)			)
       return right_rotation(UpperCAmelCase__			)
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     MyNode:
       A_		   = node.get_right()
       assert right_child is not None
       node.set_right(right_rotation(UpperCAmelCase__			)			)
       return left_rotation(UpperCAmelCase__			)
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__			)     ->     MyNode | None:
       if node is None:
              return MyNode(UpperCAmelCase__			)
       if data < node.get_data():
              node.set_left(insert_node(node.get_left(),    UpperCAmelCase__			)			)
              if (
                  get_height(node.get_left()			) - get_height(node.get_right()			) == 2
              ):  # an unbalance detected
                     A_		   = 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_		   = right_rotation(UpperCAmelCase__			)
                     else:
                            A_		   = lr_rotation(UpperCAmelCase__			)
       else:
              node.set_right(insert_node(node.get_right(),    UpperCAmelCase__			)			)
              if get_height(node.get_right()			) - get_height(node.get_left()			) == 2:
                     A_		   = node.get_right()
                     assert right_child is not None
                     if data < right_child.get_data():
                            A_		   = rl_rotation(UpperCAmelCase__			)
                     else:
                            A_		   = left_rotation(UpperCAmelCase__			)
       A_		   = my_max(get_height(node.get_right()			),    get_height(node.get_left()			)			) + 1
       node.set_height(UpperCAmelCase__			)
       return node
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     Any:
       while True:
              A_		   = root.get_right()
              if right_child is None:
                     break
              A_		   = right_child
       return root.get_data()
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     Any:
       while True:
              A_		   = root.get_left()
              if left_child is None:
                     break
              A_		   = left_child
       return root.get_data()
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__			)     ->     MyNode | None:
       A_		   = root.get_left()
       A_		   = root.get_right()
       if root.get_data() == data:
              if left_child is not None and right_child is not None:
                     A_		   = get_left_most(UpperCAmelCase__			)
                     root.set_data(UpperCAmelCase__			)
                     root.set_right(del_node(UpperCAmelCase__,    UpperCAmelCase__			)			)
              elif left_child is not None:
                     A_		   = left_child
              elif right_child is not None:
                     A_		   = 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(UpperCAmelCase__,    UpperCAmelCase__			)			)
       else:  # root.get_data() < data
              if right_child is None:
                     return root
              else:
                     root.set_right(del_node(UpperCAmelCase__,    UpperCAmelCase__			)			)

       if get_height(UpperCAmelCase__			) - get_height(UpperCAmelCase__			) == 2:
              assert right_child is not None
              if get_height(right_child.get_right()			) > get_height(right_child.get_left()			):
                     A_		   = left_rotation(UpperCAmelCase__			)
              else:
                     A_		   = rl_rotation(UpperCAmelCase__			)
       elif get_height(UpperCAmelCase__			) - get_height(UpperCAmelCase__			) == -2:
              assert left_child is not None
              if get_height(left_child.get_left()			) > get_height(left_child.get_right()			):
                     A_		   = right_rotation(UpperCAmelCase__			)
              else:
                     A_		   = lr_rotation(UpperCAmelCase__			)
       A_		   = my_max(get_height(root.get_right()			),    get_height(root.get_left()			)			) + 1
       root.set_height(UpperCAmelCase__			)
       return root


class    A__ :



    def __init__(   self    )  -> None:





           '''simple docstring'''
           A_		   = None



    def    snake_case_     (   self    )  -> int:





           '''simple docstring'''
           return get_height(self.root    )



    def    snake_case_     (   self						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           print("""insert:""" + str(UpperCamelCase__    )    )
           A_		   = insert_node(self.root						,			UpperCamelCase__    )



    def    snake_case_     (   self						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           print("""delete:""" + str(UpperCamelCase__    )    )
           if self.root is None:
                  print("""Tree is empty!"""    )
                  return
           A_		   = del_node(self.root						,			UpperCamelCase__    )







    def __str__(   self						,			)  -> str:  # a level traversale, gives a more intuitive look on the tree





           '''simple docstring'''
           A_		   = """"""
           A_		   = MyQueue()
           q.push(self.root    )
           A_		   = self.get_height()
           if layer == 0:
                  return output
           A_		   = 0
           while not q.is_empty():
                  A_		   = q.pop()
                  A_		   = """ """ * int(math.pow(2						,			layer - 1    )    )
                  output += space
                  if node is None:
                         output += "*"
                         q.push(UpperCamelCase__    )
                         q.push(UpperCamelCase__    )
                  else:
                         output += str(node.get_data()    )
                         q.push(node.get_left()    )
                         q.push(node.get_right()    )
                  output += space
                  A_		   = cnt + 1
                  for i in range(100    ):
                         if cnt == math.pow(2						,			UpperCamelCase__    ) - 1:
                                A_		   = layer - 1
                                if layer == 0:
                                       output += "\n*************************************"
                                       return output
                                output += "\n"
                                break
           output += "\n*************************************"
           return output

def  UpperCAmelCase__      ( )     ->     None:
       import doctest

       doctest.testmod()


if __name__ == "__main__":
      _test()
      __lowerCamelCase						    =      AVLtree()
      __lowerCamelCase						    =      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))



'''simple docstring'''







from __future__ import annotations

import numpy as np
from numpy import floataa
from numpy.typing import NDArray
def  UpperCAmelCase__      ( UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    UpperCAmelCase__,    )     ->     list[float]:
       A_   ,     A_		   = coefficient_matrix.shape
       A_   ,     A_		   = constant_matrix.shape

       if rowsa != colsa:
              A_		   = F'''Coefficient matrix dimensions must be nxn but received {rowsa}x{colsa}'''
              raise ValueError(UpperCAmelCase__			)

       if colsa != 1:
              A_		   = F'''Constant matrix must be nx1 but received {rowsa}x{colsa}'''
              raise ValueError(UpperCAmelCase__			)

       if rowsa != rowsa:
              A_		   = (
                  """Coefficient and constant matrices dimensions must be nxn and nx1 but """
                  F'''received {rowsa}x{colsa} and {rowsa}x{colsa}'''
              )
              raise ValueError(UpperCAmelCase__			)

       if len(UpperCAmelCase__			) != rowsa:
              A_		   = (
                  """Number of initial values must be equal to number of rows in coefficient """
                  F'''matrix but received {len(UpperCAmelCase__			)} and {rowsa}'''
              )
              raise ValueError(UpperCAmelCase__			)

       if iterations <= 0:
              raise ValueError("""Iterations must be at least 1"""			)

       A_		   = np.concatenate(
           (coefficient_matrix, constant_matrix),    axis=1			)

       A_   ,     A_		   = table.shape

       strictly_diagonally_dominant(UpperCAmelCase__			)

       # Iterates the whole matrix for given number of times
       for _ in range(UpperCAmelCase__			):
              A_		   = []
              for row in range(UpperCAmelCase__			):
                     A_		   = 0
                     for col in range(UpperCAmelCase__			):
                            if col == row:
                                   A_		   = table[row][col]
                            elif col == cols - 1:
                                   A_		   = table[row][col]
                            else:
                                   temp += (-1) * table[row][col] * init_val[col]
                     A_		   = (temp + val) / denom
                     new_val.append(UpperCAmelCase__			)
              A_		   = new_val

       return [float(UpperCAmelCase__			) for i in new_val]
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     bool:
       A_   ,     A_		   = table.shape

       A_		   = True

       for i in range(0,    UpperCAmelCase__			):
              A_		   = 0
              for j in range(0,    cols - 1			):
                     if i == j:
                            continue
                     else:
                            total += table[i][j]

              if table[i][i] <= total:
                     raise ValueError("""Coefficient matrix is not strictly diagonally dominant"""			)

       return is_diagonally_dominant


# Test Cases
if __name__ == "__main__":
      import doctest

      doctest.testmod()
