


from __future__ import annotations

import unittest
from collections.abc import Iterator


class       __lowerCAmelCase       :






  """simple docstring"""





  def __init__(       self    :    Union[str, Any]      ,			_lowerCAmelCase    :    List[Any]      ,			_lowerCAmelCase    :    int					)				->	None:




     """simple docstring"""
     snake_case_         =   label
     snake_case_         =   parent
     snake_case_         =   None
     snake_case_         =   None






class       __lowerCAmelCase       :






  """simple docstring"""





  def __init__(       self    :    List[Any]					)				->	None:




     """simple docstring"""
     snake_case_         =   None



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




     """simple docstring"""
     snake_case_         =   None



  def    lowerCAmelCase__					(       self    :    Optional[Any]					)				->	bool:




     """simple docstring"""
     return self.root is None



  def    lowerCAmelCase__					(       self    :    List[Any]      ,			_lowerCAmelCase    :    Dict					)				->	None:




     """simple docstring"""
     snake_case_         =   self._put(self.root      ,			SCREAMING_SNAKE_CASE_					)



  def    lowerCAmelCase__					(       self    :    int      ,			_lowerCAmelCase    :    List[str]      ,			_lowerCAmelCase    :    str      ,			_lowerCAmelCase    :    Tuple = None					)				->	Node:




     """simple docstring"""






     if node is None:
        snake_case_         =   Node(SCREAMING_SNAKE_CASE_      ,			SCREAMING_SNAKE_CASE_					)
     else:
        if label < node.label:
           snake_case_         =   self._put(node.left      ,			SCREAMING_SNAKE_CASE_      ,			SCREAMING_SNAKE_CASE_					)
        elif label > node.label:
           snake_case_         =   self._put(node.right      ,			SCREAMING_SNAKE_CASE_      ,			SCREAMING_SNAKE_CASE_					)
        else:
           snake_case_         =   F'''Node with label {label} already exists'''
           raise Exception(SCREAMING_SNAKE_CASE_					)

     return node



  def    lowerCAmelCase__					(       self    :    List[str]      ,			_lowerCAmelCase    :    Tuple					)				->	Node:




     """simple docstring"""
     return self._search(self.root      ,			SCREAMING_SNAKE_CASE_					)



  def    lowerCAmelCase__					(       self    :    Union[str, Any]      ,			_lowerCAmelCase    :    Union[str, Any]      ,			_lowerCAmelCase    :    Optional[int]					)				->	Node:




     """simple docstring"""






     if node is None:
        snake_case_         =   F'''Node with label {label} does not exist'''
        raise Exception(SCREAMING_SNAKE_CASE_					)
     else:
        if label < node.label:
           snake_case_         =   self._search(node.left      ,			SCREAMING_SNAKE_CASE_					)
        elif label > node.label:
           snake_case_         =   self._search(node.right      ,			SCREAMING_SNAKE_CASE_					)

     return node



  def    lowerCAmelCase__					(       self    :    Any      ,			_lowerCAmelCase    :    List[str]					)				->	None:




     """simple docstring"""
     snake_case_         =   self.search(SCREAMING_SNAKE_CASE_					)
     if node.right and node.left:
        snake_case_         =   self._get_lowest_node(node.right					)
        snake_case_         =   node.left
        snake_case_         =   node.right
        snake_case_         =   lowest_node
        if node.right:
           snake_case_         =   lowest_node
        self._reassign_nodes(SCREAMING_SNAKE_CASE_      ,			SCREAMING_SNAKE_CASE_					)
     elif not node.right and node.left:
        self._reassign_nodes(SCREAMING_SNAKE_CASE_      ,			node.left					)
     elif node.right and not node.left:
        self._reassign_nodes(SCREAMING_SNAKE_CASE_      ,			node.right					)
     else:
        self._reassign_nodes(SCREAMING_SNAKE_CASE_      ,			SCREAMING_SNAKE_CASE_					)



  def    lowerCAmelCase__					(       self    :    List[str]      ,			_lowerCAmelCase    :    Optional[int]      ,			_lowerCAmelCase    :    str					)				->	None:




     """simple docstring"""






     if new_children:
        snake_case_         =   node.parent

     if node.parent:
        if node.parent.right == node:
           snake_case_         =   new_children
        else:
           snake_case_         =   new_children
     else:
        snake_case_         =   new_children



  def    lowerCAmelCase__					(       self    :    Optional[Any]      ,			_lowerCAmelCase    :    List[Any]					)				->	Node:




     """simple docstring"""






     if node.left:
        snake_case_         =   self._get_lowest_node(node.left					)
     else:
        snake_case_         =   node
        self._reassign_nodes(SCREAMING_SNAKE_CASE_      ,			node.right					)

     return lowest_node



  def    lowerCAmelCase__					(       self    :    List[Any]      ,			_lowerCAmelCase    :    Optional[Any]					)				->	bool:




     """simple docstring"""






     try:
        self.search(SCREAMING_SNAKE_CASE_					)
        return True
     except Exception:
        return False



  def    lowerCAmelCase__					(       self    :    int					)				->	int:




     """simple docstring"""






     if self.root is None:
        raise Exception("Binary search tree is empty"					)

     snake_case_         =   self.root
     while node.right is not None:
        snake_case_         =   node.right

     return node.label



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




     """simple docstring"""






     if self.root is None:
        raise Exception("Binary search tree is empty"					)

     snake_case_         =   self.root
     while node.left is not None:
        snake_case_         =   node.left

     return node.label



  def    lowerCAmelCase__					(       self    :    Optional[Any]					)				->	Iterator[Node]:




     """simple docstring"""
     return self._inorder_traversal(self.root					)



  def    lowerCAmelCase__					(       self    :    Optional[int]      ,			_lowerCAmelCase    :    int					)				->	Iterator[Node]:




     """simple docstring"""






     if node is not None:
        yield from self._inorder_traversal(node.left					)
        yield node
        yield from self._inorder_traversal(node.right					)



  def    lowerCAmelCase__					(       self    :    Optional[int]					)				->	Iterator[Node]:




     """simple docstring"""
     return self._preorder_traversal(self.root					)



  def    lowerCAmelCase__					(       self    :    Any      ,			_lowerCAmelCase    :    Any					)				->	Iterator[Node]:




     """simple docstring"""






     if node is not None:
        yield node
        yield from self._preorder_traversal(node.left					)
        yield from self._preorder_traversal(node.right					)






class       __lowerCAmelCase       (	unittest.TestCase   ):






  """simple docstring"""





  @staticmethod
  def    lowerCAmelCase__					(       )				->	BinarySearchTree:




     """simple docstring"""
     snake_case_         =   BinarySearchTree()
     t.put(8					)
     t.put(3					)
     t.put(6					)
     t.put(1					)
     t.put(1_0					)
     t.put(1_4					)
     t.put(1_3					)
     t.put(4					)
     t.put(7					)
     t.put(5					)

     return t



  def    lowerCAmelCase__					(       self    :    List[str]					)				->	None:




     """simple docstring"""
     snake_case_         =   BinarySearchTree()
     assert t.is_empty()

     t.put(8					)
     assert t.root is not None
     assert t.root.parent is None
     assert t.root.label == 8

     t.put(1_0					)
     assert t.root.right is not None
     assert t.root.right.parent == t.root
     assert t.root.right.label == 1_0

     t.put(3					)
     assert t.root.left is not None
     assert t.root.left.parent == t.root
     assert t.root.left.label == 3

     t.put(6					)
     assert t.root.left.right is not None
     assert t.root.left.right.parent == t.root.left
     assert t.root.left.right.label == 6

     t.put(1					)
     assert t.root.left.left is not None
     assert t.root.left.left.parent == t.root.left
     assert t.root.left.left.label == 1

     with self.assertRaises(SCREAMING_SNAKE_CASE_					):  # noqa: B017
        t.put(1					)



  def    lowerCAmelCase__					(       self    :    Tuple					)				->	None:




     """simple docstring"""
     snake_case_         =   self._get_binary_search_tree()

     snake_case_         =   t.search(6					)
     assert node.label == 6

     snake_case_         =   t.search(1_3					)
     assert node.label == 1_3

     with self.assertRaises(SCREAMING_SNAKE_CASE_					):  # noqa: B017
        t.search(2					)



  def    lowerCAmelCase__					(       self    :    Dict					)				->	None:




     """simple docstring"""
     snake_case_         =   self._get_binary_search_tree()

     t.remove(1_3					)
     assert t.root is not None
     assert t.root.right is not None
     assert t.root.right.right is not None
     assert t.root.right.right.right is None
     assert t.root.right.right.left is None

     t.remove(7					)
     assert t.root.left is not None
     assert t.root.left.right is not None
     assert t.root.left.right.left is not None
     assert t.root.left.right.right is None
     assert t.root.left.right.left.label == 4

     t.remove(6					)
     assert t.root.left.left is not None
     assert t.root.left.right.right is not None
     assert t.root.left.left.label == 1
     assert t.root.left.right.label == 4
     assert t.root.left.right.right.label == 5
     assert t.root.left.right.left is None
     assert t.root.left.left.parent == t.root.left
     assert t.root.left.right.parent == t.root.left

     t.remove(3					)
     assert t.root is not None
     assert t.root.left.label == 4
     assert t.root.left.right.label == 5
     assert t.root.left.left.label == 1
     assert t.root.left.parent == t.root
     assert t.root.left.left.parent == t.root.left
     assert t.root.left.right.parent == t.root.left

     t.remove(4					)
     assert t.root.left is not None
     assert t.root.left.left is not None
     assert t.root.left.label == 5
     assert t.root.left.right is None
     assert t.root.left.left.label == 1
     assert t.root.left.parent == t.root
     assert t.root.left.left.parent == t.root.left



  def    lowerCAmelCase__					(       self    :    Any					)				->	None:




     """simple docstring"""
     snake_case_         =   self._get_binary_search_tree()

     t.remove(3					)
     assert t.root is not None
     assert t.root.left is not None
     assert t.root.left.left is not None
     assert t.root.left.right is not None
     assert t.root.left.right.left is not None
     assert t.root.left.right.right is not None
     assert t.root.left.label == 4
     assert t.root.left.right.label == 6
     assert t.root.left.left.label == 1
     assert t.root.left.right.right.label == 7
     assert t.root.left.right.left.label == 5
     assert t.root.left.parent == t.root
     assert t.root.left.right.parent == t.root.left
     assert t.root.left.left.parent == t.root.left
     assert t.root.left.right.left.parent == t.root.left.right



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




     """simple docstring"""
     snake_case_         =   self._get_binary_search_tree()
     t.empty()
     assert t.root is None



  def    lowerCAmelCase__					(       self    :    Tuple					)				->	None:




     """simple docstring"""
     snake_case_         =   self._get_binary_search_tree()
     assert not t.is_empty()

     t.empty()
     assert t.is_empty()



  def    lowerCAmelCase__					(       self    :    Tuple					)				->	None:




     """simple docstring"""
     snake_case_         =   self._get_binary_search_tree()

     assert t.exists(6					)
     assert not t.exists(-1					)



  def    lowerCAmelCase__					(       self    :    Optional[int]					)				->	None:




     """simple docstring"""
     snake_case_         =   self._get_binary_search_tree()

     assert t.get_max_label() == 1_4

     t.empty()
     with self.assertRaises(SCREAMING_SNAKE_CASE_					):  # noqa: B017
        t.get_max_label()



  def    lowerCAmelCase__					(       self    :    int					)				->	None:




     """simple docstring"""
     snake_case_         =   self._get_binary_search_tree()

     assert t.get_min_label() == 1

     t.empty()
     with self.assertRaises(SCREAMING_SNAKE_CASE_					):  # noqa: B017
        t.get_min_label()



  def    lowerCAmelCase__					(       self    :    Any					)				->	None:




     """simple docstring"""
     snake_case_         =   self._get_binary_search_tree()

     snake_case_         =   [i.label for i in t.inorder_traversal()]
     assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]



  def    lowerCAmelCase__					(       self    :    str					)				->	None:




     """simple docstring"""
     snake_case_         =   self._get_binary_search_tree()

     snake_case_         =   [i.label for i in t.preorder_traversal()]
     assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]






def      _lowerCAmelCase  (							)->None:
   '''simple docstring'''






   snake_case_         =   BinarySearchTree()
   t.put(8							)
   t.put(3							)
   t.put(6							)
   t.put(1							)
   t.put(10							)
   t.put(14							)
   t.put(13							)
   t.put(4							)
   t.put(7							)
   t.put(5							)

   print(
       "\n            8\n           / \\\n          3   10\n         / \\    \\\n        1   6    14\n           / \\   /\n          4   7 13\n           \\\n            5\n        "							)

   print("Label 6 exists:"						,  t.exists(6							)							)
   print("Label 13 exists:"						,  t.exists(13							)							)
   print("Label -1 exists:"						,  t.exists(-1							)							)
   print("Label 12 exists:"						,  t.exists(12							)							)

   # Prints all the elements of the list in inorder traversal
   snake_case_         =   [i.label for i in t.inorder_traversal()]
   print("Inorder traversal:"						,  lowerCAmelCase_							)

   # Prints all the elements of the list in preorder traversal
   snake_case_         =   [i.label for i in t.preorder_traversal()]
   print("Preorder traversal:"						,  lowerCAmelCase_							)

   print("Max. label:"						,  t.get_max_label()							)
   print("Min. label:"						,  t.get_min_label()							)

   # Delete elements
   print("\nDeleting elements 13, 10, 8, 3, 6, 14"							)
   print(
       "\n          4\n         / \\\n        1   7\n             \\\n              5\n        "							)
   t.remove(13							)
   t.remove(10							)
   t.remove(8							)
   t.remove(3							)
   t.remove(6							)
   t.remove(14							)

   # Prints all the elements of the list in inorder traversal after delete
   snake_case_         =   [i.label for i in t.inorder_traversal()]
   print("Inorder traversal after delete:"						,  lowerCAmelCase_							)

   # Prints all the elements of the list in preorder traversal after delete
   snake_case_         =   [i.label for i in t.preorder_traversal()]
   print("Preorder traversal after delete:"						,  lowerCAmelCase_							)

   print("Max. label:"						,  t.get_max_label()							)
   print("Min. label:"						,  t.get_min_label()							)


if __name__ == "__main__":
   binary_search_tree_example()







import numpy as np
from cva import destroyAllWindows, imread, imshow, waitKey


class       __lowerCAmelCase       :






  """simple docstring"""





  def __init__(       self    :    Optional[Any]      ,			_lowerCAmelCase    :    Union[str, Any]      ,			_lowerCAmelCase    :    int					)				->	Tuple:




     """simple docstring"""
     snake_case_         =   0
     # max greyscale value for #FFFFFF
     snake_case_         =   int(self.get_greyscale(2_5_5      ,			2_5_5      ,			2_5_5					)					)

     if not self.min_threshold < threshold < self.max_threshold:
        snake_case_         =   F'''Factor value should be from 0 to {self.max_threshold}'''
        raise ValueError(_lowerCAmelCase					)

     snake_case_         =   input_img
     snake_case_         =   threshold
     snake_case_      ,      snake_case_         =   self.input_img.shape[1], self.input_img.shape[0]

     # error table size (+4 columns and +1 row) greater than input image because of
     # lack of if statements
     snake_case_         =   [
         [0 for _ in range(self.height + 4					)] for __ in range(self.width + 1					)
     ]
     snake_case_         =   np.ones((self.width, self.height, 3)      ,			np.uinta					) * 2_5_5



  @classmethod
  def    lowerCAmelCase__					(       cls    :    Optional[Any]      ,			_lowerCAmelCase    :    int      ,			_lowerCAmelCase    :    int      ,			_lowerCAmelCase    :    int					)				->	float:




     """simple docstring"""
     return 0.114 * blue + 0.587 * green + 0.2_126 * red



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




     """simple docstring"""
     for y in range(self.height					):
        for x in range(self.width					):
           snake_case_         =   int(self.get_greyscale(*self.input_img[y][x]					)					)
           if self.threshold > greyscale + self.error_table[y][x]:
              snake_case_         =   (0, 0, 0)
              snake_case_         =   greyscale + self.error_table[x][y]
           else:
              snake_case_         =   (2_5_5, 2_5_5, 2_5_5)
              snake_case_         =   greyscale + self.error_table[x][y] - 2_5_5
           self.error_table[y][x + 1] += int(8 / 3_2 * current_error					)
           self.error_table[y][x + 2] += int(4 / 3_2 * current_error					)
           self.error_table[y + 1][x] += int(8 / 3_2 * current_error					)
           self.error_table[y + 1][x + 1] += int(4 / 3_2 * current_error					)
           self.error_table[y + 1][x + 2] += int(2 / 3_2 * current_error					)
           self.error_table[y + 1][x - 1] += int(4 / 3_2 * current_error					)
           self.error_table[y + 1][x - 2] += int(2 / 3_2 * current_error					)


if __name__ == "__main__":
   # create Burke's instances with original images in greyscale
   SCREAMING_SNAKE_CASE		:Dict											=       [
       Burkes(imread('''image_data/lena.jpg''', 1), threshold)
       for threshold in (1, 1_26, 1_30, 1_40)
   ]

   for burkes in burkes_instances:
      burkes.process()

   for burkes in burkes_instances:
      imshow(
          F'''Original image with dithering threshold: {burkes.threshold}''',
          burkes.output_img,
      )

   waitKey(0)
   destroyAllWindows()




