





"""simple docstring"""
from __future__ import annotations

import math
import random
from typing import Any






class 					_SCREAMING_SNAKE_CASE:




       def __init__(						self							)			->      None:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Dict						=  []
             __SCREAMING_SNAKE_CASE   :Tuple						=  0
             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  0




       def     _UpperCamelCase     (						self							)			->      bool:





             """simple docstring"""






             return self.head == self.tail




       def     _UpperCamelCase     (						self		,SCREAMING_SNAKE_CASE__							)			->      None:





             """simple docstring"""






             self.data.append(_a							)
             __SCREAMING_SNAKE_CASE   :Tuple						=  self.tail + 1




       def     _UpperCamelCase     (						self							)			->      Any:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Dict						=  self.data[self.head]
             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  self.head + 1
             return ret




       def     _UpperCamelCase     (						self							)			->      int:





             """simple docstring"""






             return self.tail - self.head




       def     _UpperCamelCase     (						self							)			->      None:





             """simple docstring"""






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






class 					_SCREAMING_SNAKE_CASE:




       def __init__(						self		,SCREAMING_SNAKE_CASE__							)			->      None:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :List[Any]						=  data
             __SCREAMING_SNAKE_CASE   :Tuple						=  None
             __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  None
             __SCREAMING_SNAKE_CASE   :List[Any]						=  1




       def     _UpperCamelCase     (						self							)			->      Any:





             """simple docstring"""






             return self.data




       def     _UpperCamelCase     (						self							)			->      MyNode | None:





             """simple docstring"""






             return self.left




       def     _UpperCamelCase     (						self							)			->      MyNode | None:





             """simple docstring"""






             return self.right




       def     _UpperCamelCase     (						self							)			->      int:





             """simple docstring"""






             return self.height




       def     _UpperCamelCase     (						self		,SCREAMING_SNAKE_CASE__							)			->      None:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Optional[int]						=  data




       def     _UpperCamelCase     (						self		,SCREAMING_SNAKE_CASE__							)			->      None:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Tuple						=  node




       def     _UpperCamelCase     (						self		,SCREAMING_SNAKE_CASE__							)			->      None:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  node




       def     _UpperCamelCase     (						self		,SCREAMING_SNAKE_CASE__							)			->      None:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  height




def      __lowerCamelCase   (							a_     :		MyNode | None							)			->      int:




      if node is None:
            return 0
      return node.get_height()



def      __lowerCamelCase   (							a_     :		int ,   a_     :		int							)			->      int:




      if a > b:
            return a
      return b



def      __lowerCamelCase   (							a_     :		MyNode							)			->      MyNode:
      print('''left rotation node:''' ,   node.get_data()							)
      __SCREAMING_SNAKE_CASE   :Optional[Any]						=  node.get_left()
      assert ret is not None
      node.set_left(ret.get_right()							)
      ret.set_right(_UpperCamelCase							)
      __SCREAMING_SNAKE_CASE   :List[str]						=  my_max(get_height(node.get_right()							) ,   get_height(node.get_left()							)							) + 1
      node.set_height(_UpperCamelCase							)
      __SCREAMING_SNAKE_CASE   :List[Any]						=  my_max(get_height(ret.get_right()							) ,   get_height(ret.get_left()							)							) + 1
      ret.set_height(_UpperCamelCase							)
      return ret



def      __lowerCamelCase   (							a_     :		MyNode							)			->      MyNode:
      print('''right rotation node:''' ,   node.get_data()							)
      __SCREAMING_SNAKE_CASE   :Dict						=  node.get_right()
      assert ret is not None
      node.set_right(ret.get_left()							)
      ret.set_left(_UpperCamelCase							)
      __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  my_max(get_height(node.get_right()							) ,   get_height(node.get_left()							)							) + 1
      node.set_height(_UpperCamelCase							)
      __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  my_max(get_height(ret.get_right()							) ,   get_height(ret.get_left()							)							) + 1
      ret.set_height(_UpperCamelCase							)
      return ret



def      __lowerCamelCase   (							a_     :		MyNode							)			->      MyNode:
      __SCREAMING_SNAKE_CASE   :Tuple						=  node.get_left()
      assert left_child is not None
      node.set_left(left_rotation(_UpperCamelCase							)							)
      return right_rotation(_UpperCamelCase							)



def      __lowerCamelCase   (							a_     :		MyNode							)			->      MyNode:
      __SCREAMING_SNAKE_CASE   :Optional[Any]						=  node.get_right()
      assert right_child is not None
      node.set_right(right_rotation(_UpperCamelCase							)							)
      return left_rotation(_UpperCamelCase							)



def      __lowerCamelCase   (							a_     :		MyNode | None ,   a_     :		Any							)			->      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
                  __SCREAMING_SNAKE_CASE   :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
                        __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  right_rotation(_UpperCamelCase							)
                  else:
                        __SCREAMING_SNAKE_CASE   :Dict						=  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:
                  __SCREAMING_SNAKE_CASE   :Optional[Any]						=  node.get_right()
                  assert right_child is not None
                  if data < right_child.get_data():
                        __SCREAMING_SNAKE_CASE   :Dict						=  rl_rotation(_UpperCamelCase							)
                  else:
                        __SCREAMING_SNAKE_CASE   :str						=  left_rotation(_UpperCamelCase							)
      __SCREAMING_SNAKE_CASE   :str						=  my_max(get_height(node.get_right()							) ,   get_height(node.get_left()							)							) + 1
      node.set_height(_UpperCamelCase							)
      return node



def      __lowerCamelCase   (							a_     :		MyNode							)			->      Any:




      while True:
            __SCREAMING_SNAKE_CASE   :Tuple						=  root.get_right()
            if right_child is None:
                  break
            __SCREAMING_SNAKE_CASE   :Optional[Any]						=  right_child
      return root.get_data()



def      __lowerCamelCase   (							a_     :		MyNode							)			->      Any:




      while True:
            __SCREAMING_SNAKE_CASE   :Dict						=  root.get_left()
            if left_child is None:
                  break
            __SCREAMING_SNAKE_CASE   :Optional[Any]						=  left_child
      return root.get_data()



def      __lowerCamelCase   (							a_     :		MyNode ,   a_     :		Any							)			->      MyNode | None:
      __SCREAMING_SNAKE_CASE   :List[str]						=  root.get_left()
      __SCREAMING_SNAKE_CASE   :List[Any]						=  root.get_right()
      if root.get_data() == data:
            if left_child is not None and right_child is not None:
                  __SCREAMING_SNAKE_CASE   :List[str]						=  get_left_most(_UpperCamelCase							)
                  root.set_data(_UpperCamelCase							)
                  root.set_right(del_node(_UpperCamelCase ,   _UpperCamelCase							)							)
            elif left_child is not None:
                  __SCREAMING_SNAKE_CASE   :List[str]						=  left_child
            elif right_child is not None:
                  __SCREAMING_SNAKE_CASE   :int						=  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()							):
                  __SCREAMING_SNAKE_CASE   :int						=  left_rotation(_UpperCamelCase							)
            else:
                  __SCREAMING_SNAKE_CASE   :int						=  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()							):
                  __SCREAMING_SNAKE_CASE   :Optional[int]						=  right_rotation(_UpperCamelCase							)
            else:
                  __SCREAMING_SNAKE_CASE   :List[str]						=  lr_rotation(_UpperCamelCase							)
      __SCREAMING_SNAKE_CASE   :Optional[int]						=  my_max(get_height(root.get_right()							) ,   get_height(root.get_left()							)							) + 1
      root.set_height(_UpperCamelCase							)
      return root






class 					_SCREAMING_SNAKE_CASE:




       def __init__(						self							)			->      None:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :int						=  None




       def     _UpperCamelCase     (						self							)			->      int:





             """simple docstring"""






             return get_height(self.root							)




       def     _UpperCamelCase     (						self		,SCREAMING_SNAKE_CASE__							)			->      None:





             """simple docstring"""






             print('''insert:''' + str(_a							)							)
             __SCREAMING_SNAKE_CASE   :Tuple						=  insert_node(self.root		,_a							)




       def     _UpperCamelCase     (						self		,SCREAMING_SNAKE_CASE__							)			->      None:





             """simple docstring"""






             print('''delete:''' + str(_a							)							)
             if self.root is None:
                   print('''Tree is empty!'''							)
                   return
             __SCREAMING_SNAKE_CASE   :Optional[int]						=  del_node(self.root		,_a							)




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





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Tuple						=  ''''''
             __SCREAMING_SNAKE_CASE   :List[Any]						=  MyQueue()
             q.push(self.root							)
             __SCREAMING_SNAKE_CASE   :Optional[int]						=  self.get_height()
             if layer == 0:
                   return output
             __SCREAMING_SNAKE_CASE   :int						=  0
             while not q.is_empty():
                   __SCREAMING_SNAKE_CASE   :Any						=  q.pop()
                   __SCREAMING_SNAKE_CASE   :int						=  ''' ''' * int(math.pow(2		,layer - 1							)							)
                   output += space
                   if node is None:
                         output += "*"
                         q.push(_a							)
                         q.push(_a							)
                   else:
                         output += str(node.get_data()							)
                         q.push(node.get_left()							)
                         q.push(node.get_right()							)
                   output += space
                   __SCREAMING_SNAKE_CASE   :Tuple						=  cnt + 1
                   for i in range(1_00							):
                         if cnt == math.pow(2		,_a							) - 1:
                               __SCREAMING_SNAKE_CASE   :List[str]						=  layer - 1
                               if layer == 0:
                                     output += "\n*************************************"
                                     return output
                               output += "\n"
                               break
             output += "\n*************************************"
             return output




def      __lowerCamelCase   (							)			->      None:
      import doctest

      doctest.testmod()


if __name__ == "__main__":
  _test()
  lowerCamelCase_								=		AVLtree()
  lowerCamelCase_								=		list(range(1_0))
  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'''
import numpy as np
from PIL import Image


def        _lowerCAmelCase					(						_UpperCamelCase						:     np.ndarray							, _UpperCamelCase						:     int							, _UpperCamelCase						:     int				)      ->			np.ndarray:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =np.array(_UpperCamelCase				)
     if arr.shape[0] != arr.shape[1]:
          raise ValueError('The input array is not a square matrix'				)
     _SCREAMING_SNAKE_CASE							    =0
     _SCREAMING_SNAKE_CASE							    =0
     _SCREAMING_SNAKE_CASE							    =0
     _SCREAMING_SNAKE_CASE							    =0

     # compute the shape of the output matrix
     _SCREAMING_SNAKE_CASE							    =(arr.shape[0] - size) // stride + 1
     # initialize the output matrix with zeros of shape maxpool_shape
     _SCREAMING_SNAKE_CASE							    =np.zeros((maxpool_shape, maxpool_shape)				)

     while i < arr.shape[0]:
          if i + size > arr.shape[0]:
               # if the end of the matrix is reached, break
               break
          while j < arr.shape[1]:
               # if the end of the matrix is reached, break
               if j + size > arr.shape[1]:
                    break
               # compute the maximum of the pooling matrix
               _SCREAMING_SNAKE_CASE							    =np.max(arr[i : i + size, j : j + size]				)
               # shift the pooling matrix by stride of column pixels
               j += stride
               mat_j += 1

          # shift the pooling matrix by stride of row pixels
          i += stride
          mat_i += 1

          # reset the column index to 0
          _SCREAMING_SNAKE_CASE							    =0
          _SCREAMING_SNAKE_CASE							    =0

     return updated_arr


def        _lowerCAmelCase					(						_UpperCamelCase						:     np.ndarray							, _UpperCamelCase						:     int							, _UpperCamelCase						:     int				)      ->			np.ndarray:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =np.array(_UpperCamelCase				)
     if arr.shape[0] != arr.shape[1]:
          raise ValueError('The input array is not a square matrix'				)
     _SCREAMING_SNAKE_CASE							    =0
     _SCREAMING_SNAKE_CASE							    =0
     _SCREAMING_SNAKE_CASE							    =0
     _SCREAMING_SNAKE_CASE							    =0

     # compute the shape of the output matrix
     _SCREAMING_SNAKE_CASE							    =(arr.shape[0] - size) // stride + 1
     # initialize the output matrix with zeros of shape avgpool_shape
     _SCREAMING_SNAKE_CASE							    =np.zeros((avgpool_shape, avgpool_shape)				)

     while i < arr.shape[0]:
          # if the end of the matrix is reached, break
          if i + size > arr.shape[0]:
               break
          while j < arr.shape[1]:
               # if the end of the matrix is reached, break
               if j + size > arr.shape[1]:
                    break
               # compute the average of the pooling matrix
               _SCREAMING_SNAKE_CASE							    =int(np.average(arr[i : i + size, j : j + size]				)				)
               # shift the pooling matrix by stride of column pixels
               j += stride
               mat_j += 1

          # shift the pooling matrix by stride of row pixels
          i += stride
          mat_i += 1
          # reset the column index to 0
          _SCREAMING_SNAKE_CASE							    =0
          _SCREAMING_SNAKE_CASE							    =0

     return updated_arr


# Main Function
if __name__ == "__main__":
     from doctest import testmod

     testmod(name="avgpooling", verbose=True)

     # Loading the image
     lowerCamelCase :      Optional[Any]					 =     Image.open("path_to_image")

     # Converting the image to numpy array and maxpooling, displaying the result
     # Ensure that the image is a square matrix

     Image.fromarray(maxpooling(np.array(image), size=3, stride=2)).show()

     # Converting the image to numpy array and averagepooling, displaying the result
     # Ensure that the image is a square matrix

     Image.fromarray(avgpooling(np.array(image), size=3, stride=2)).show()
