'''simple docstring'''




from __future__ import annotations

import unittest
from collections.abc import Iterator

class 			lowerCamelCase_			:
      '''simple docstring'''

      def __init__( self		:       Union[str, Any]		,      A		:       int		,      A		:       Node | None ):
             _UpperCAmelCase  :						Optional[Any]							   =					label
             _UpperCAmelCase  :						Dict							   =					parent
             _UpperCAmelCase  :						Node | None							   =					None
             _UpperCAmelCase  :						Node | None							   =					None

class 			lowerCamelCase_			:
      '''simple docstring'''

      def __init__( self		:       Union[str, Any] ):
             _UpperCAmelCase  :						Node | None							   =					None




      def   _A			( self		:       int ):
             _UpperCAmelCase  :						int							   =					None




      def   _A			( self		:       Optional[Any] ):
             return self.root is None




      def   _A			( self		:       Union[str, Any]		,      A		:       int ):
             _UpperCAmelCase  :						str							   =					self._put(self.root		,      A )




      def   _A			( self		:       Optional[int]		,      A		:       Node | None		,      A		:       int		,      A		:       Node | None = None ):
             if node is None:
                    _UpperCAmelCase  :						Optional[int]							   =					Node(A		,      A )
             else:
                    if label < node.label:
                           _UpperCAmelCase  :						Tuple							   =					self._put(node.left		,      A		,      A )
                    elif label > node.label:
                           _UpperCAmelCase  :						str							   =					self._put(node.right		,      A		,      A )
                    else:
                           _UpperCAmelCase  :						List[str]							   =					F"""Node with label {label} already exists"""
                           raise Exception(A )

             return node




      def   _A			( self		:       List[Any]		,      A		:       int ):
             return self._search(self.root		,      A )




      def   _A			( self		:       Any		,      A		:       Node | None		,      A		:       int ):
             if node is None:
                    _UpperCAmelCase  :						Optional[Any]							   =					F"""Node with label {label} does not exist"""
                    raise Exception(A )
             else:
                    if label < node.label:
                           _UpperCAmelCase  :						Optional[int]							   =					self._search(node.left		,      A )
                    elif label > node.label:
                           _UpperCAmelCase  :						str							   =					self._search(node.right		,      A )

             return node




      def   _A			( self		:       List[Any]		,      A		:       int ):
             _UpperCAmelCase  :						int							   =					self.search(A )
             if node.right and node.left:
                    _UpperCAmelCase  :						Any							   =					self._get_lowest_node(node.right )
                    _UpperCAmelCase  :						Dict							   =					node.left
                    _UpperCAmelCase  :						List[Any]							   =					node.right
                    _UpperCAmelCase  :						Optional[Any]							   =					lowest_node
                    if node.right:
                           _UpperCAmelCase  :						List[Any]							   =					lowest_node
                    self._reassign_nodes(A		,      A )
             elif not node.right and node.left:
                    self._reassign_nodes(A		,      node.left )
             elif node.right and not node.left:
                    self._reassign_nodes(A		,      node.right )
             else:
                    self._reassign_nodes(A		,      A )




      def   _A			( self		:       Optional[Any]		,      A		:       Node		,      A		:       Node | None ):
             if new_children:
                    _UpperCAmelCase  :						str							   =					node.parent

             if node.parent:
                    if node.parent.right == node:
                           _UpperCAmelCase  :						str							   =					new_children
                    else:
                           _UpperCAmelCase  :						Tuple							   =					new_children
             else:
                    _UpperCAmelCase  :						Union[str, Any]							   =					new_children




      def   _A			( self		:       Dict		,      A		:       Node ):
             if node.left:
                    _UpperCAmelCase  :						List[Any]							   =					self._get_lowest_node(node.left )
             else:
                    _UpperCAmelCase  :						Optional[Any]							   =					node
                    self._reassign_nodes(A		,      node.right )

             return lowest_node




      def   _A			( self		:       int		,      A		:       int ):
             try:
                    self.search(A )
                    return True
             except Exception:
                    return False




      def   _A			( self		:       Union[str, Any] ):
             if self.root is None:
                    raise Exception("Binary search tree is empty" )

             _UpperCAmelCase  :						Any							   =					self.root
             while node.right is not None:
                    _UpperCAmelCase  :						int							   =					node.right

             return node.label




      def   _A			( self		:       Optional[Any] ):
             if self.root is None:
                    raise Exception("Binary search tree is empty" )

             _UpperCAmelCase  :						Union[str, Any]							   =					self.root
             while node.left is not None:
                    _UpperCAmelCase  :						str							   =					node.left

             return node.label




      def   _A			( self		:       Optional[int] ):
             return self._inorder_traversal(self.root )




      def   _A			( self		:       List[Any]		,      A		:       Node | None ):
             if node is not None:
                    yield from self._inorder_traversal(node.left )
                    yield node
                    yield from self._inorder_traversal(node.right )




      def   _A			( self		:       Tuple ):
             return self._preorder_traversal(self.root )





      def   _A			( self		:       Optional[int]		,      A		:       Node | None ):
             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   _A			( ):
             _UpperCAmelCase  :						List[str]							   =					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 )

             return t




      def   _A			( self		:       Optional[int] ):
             _UpperCAmelCase  :						List[Any]							   =					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(10 )
             assert t.root.right is not None
             assert t.root.right.parent == t.root
             assert t.root.right.label == 10

             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(A ):  # noqa: B017
                    t.put(1 )




      def   _A			( self		:       List[Any] ):
             _UpperCAmelCase  :						Optional[Any]							   =					self._get_binary_search_tree()

             _UpperCAmelCase  :						Tuple							   =					t.search(6 )
             assert node.label == 6

             _UpperCAmelCase  :						int							   =					t.search(13 )
             assert node.label == 13

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




      def   _A			( self		:       List[Any] ):
             _UpperCAmelCase  :						Dict							   =					self._get_binary_search_tree()

             t.remove(13 )
             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   _A			( self		:       List[Any] ):
             _UpperCAmelCase  :						str							   =					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   _A			( self		:       int ):
             _UpperCAmelCase  :						Tuple							   =					self._get_binary_search_tree()
             t.empty()
             assert t.root is None




      def   _A			( self		:       Union[str, Any] ):
             _UpperCAmelCase  :						Dict							   =					self._get_binary_search_tree()
             assert not t.is_empty()

             t.empty()
             assert t.is_empty()




      def   _A			( self		:       Any ):
             _UpperCAmelCase  :						Dict							   =					self._get_binary_search_tree()

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




      def   _A			( self		:       Any ):
             _UpperCAmelCase  :						Any							   =					self._get_binary_search_tree()

             assert t.get_max_label() == 14

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




      def   _A			( self		:       Union[str, Any] ):
             _UpperCAmelCase  :						Any							   =					self._get_binary_search_tree()

             assert t.get_min_label() == 1

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




      def   _A			( self		:       List[str] ):
             _UpperCAmelCase  :						List[Any]							   =					self._get_binary_search_tree()

             _UpperCAmelCase  :						str							   =					[i.label for i in t.inorder_traversal()]
             assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]





      def   _A			( self		:       str ):
             _UpperCAmelCase  :						Optional[Any]							   =					self._get_binary_search_tree()

             _UpperCAmelCase  :						Any							   =					[i.label for i in t.preorder_traversal()]
             assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]

def 			UpperCamelCase_							(      )					->					None:


       """simple docstring"""







       _UpperCAmelCase  :						Tuple							   =					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
       _UpperCAmelCase  :						int							   =					[i.label for i in t.inorder_traversal()]
       print("Inorder traversal:"    ,			_UpperCAmelCase					)

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

       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
       _UpperCAmelCase  :						str							   =					[i.label for i in t.inorder_traversal()]
       print("Inorder traversal after delete:"    ,			_UpperCAmelCase					)

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

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


if __name__ == "__main__":
  binary_search_tree_example()


'''simple docstring'''




from typing import Any

import numpy as np

class 			lowerCamelCase_			:
      '''simple docstring'''

      def __init__( self		:       Optional[int]		,      A		:       np.ndarray		,      A		:       int ):
             # Check if RHS is negative
             if np.any(tableau[:, -1]		,      where=tableau[:, -1] < 0 ):
                    raise ValueError("RHS must be > 0" )

             _UpperCAmelCase  :						Union[str, Any]							   =					tableau
             _UpperCAmelCase   ,						_UpperCAmelCase  :						str							   =					tableau.shape

             # Number of decision variables x1, x2, x3...
             _UpperCAmelCase  :						Any							   =					n_vars

             # Number of artificial variables to be minimised
             _UpperCAmelCase  :						List[str]							   =					len(np.where(tableau[self.n_vars : -1] == -1 )[0] )

             # 2 if there are >= or == constraints (nonstandard), 1 otherwise (std)
             _UpperCAmelCase  :						List[Any]							   =					(self.n_art_vars > 0) + 1

             # Number of slack variables added to make inequalities into equalities
             _UpperCAmelCase  :						int							   =					self.n_rows - self.n_stages

             # Objectives for each stage
             _UpperCAmelCase  :						Optional[Any]							   =					["max"]

             # In two stage simplex, first minimise then maximise
             if self.n_art_vars:
                    self.objectives.append("min" )

             _UpperCAmelCase  :						Any							   =					[""]

             # Index of current pivot row and column
             _UpperCAmelCase  :						Optional[Any]							   =					None
             _UpperCAmelCase  :						Dict							   =					None

             # Does objective row only contain (non)-negative values?
             _UpperCAmelCase  :						List[str]							   =					False




      @staticmethod
      def   _A			( *A		:       int ):
             if len(A ) != 3:
                    raise ValueError("Must provide n_vars, n_slack, and n_art_vars" )

             if not all(x >= 0 and isinstance(A		,      A ) for x in args ):
                    raise ValueError("All arguments must be non-negative integers" )

             # decision | slack | artificial
             _UpperCAmelCase  :						Optional[Any]							   =					["x", "s", "a"]
             _UpperCAmelCase  :						int							   =					[]
             for i in range(3 ):
                    for j in range(args[i] ):
                           titles.append(string_starts[i] + str(j + 1 ) )
             titles.append("RHS" )
             return titles




      def   _A			( self		:       List[str]		,      A		:       np.ndarray ):
             _UpperCAmelCase  :						str							   =					self.objectives[-1]

             # Find entries of highest magnitude in objective rows
             _UpperCAmelCase  :						List[str]							   =					(objective == "min") - (objective == "max")
             _UpperCAmelCase  :						Optional[Any]							   =					np.argmax(sign * tableau[0, : self.n_vars] )

             # Choice is only valid if below 0 for maximise, and above for minimise
             if sign * self.tableau[0, col_idx] <= 0:
                    _UpperCAmelCase  :						Dict							   =					True
                    return 0, 0

             # Pivot row is chosen as having the lowest quotient when elements of
             # the pivot column divide the right-hand side

             # Slice excluding the objective rows
             _UpperCAmelCase  :						Any							   =					slice(self.n_stages		,      self.n_rows )

             # RHS
             _UpperCAmelCase  :						Optional[Any]							   =					tableau[s, -1]

             # Elements of pivot column within slice
             _UpperCAmelCase  :						Optional[Any]							   =					tableau[s, col_idx]

             # Array filled with nans
             _UpperCAmelCase  :						List[Any]							   =					np.full(self.n_rows - self.n_stages		,      np.nan )

             # If element in pivot column is greater than zeron_stages, return
             # quotient or nan otherwise
             _UpperCAmelCase  :						str							   =					np.divide(A		,      A		,      out=A		,      where=divisor > 0 )

             # Arg of minimum quotient excluding the nan values. n_stages is added
             # to compensate for earlier exclusion of objective columns
             _UpperCAmelCase  :						Optional[Any]							   =					np.nanargmin(A ) + self.n_stages
             return row_idx, col_idx




      def   _A			( self		:       List[Any]		,      A		:       np.ndarray		,      A		:       int		,      A		:       int ):
             _UpperCAmelCase  :						Union[str, Any]							   =					tableau[row_idx].copy()

             _UpperCAmelCase  :						Optional[Any]							   =					piv_row[col_idx]

             # Entry becomes 1
             piv_row *= 1 / piv_val

             # Variable in pivot column becomes basic, ie the only non-zero entry
             for idx, coeff in enumerate(tableau[:, col_idx] ):
                    tableau[idx] += -coeff * piv_row
             _UpperCAmelCase  :						Optional[Any]							   =					piv_row
             return tableau




      def   _A			( self		:       Optional[Any]		,      A		:       np.ndarray ):
             self.objectives.pop()

             if not self.objectives:
                    return tableau

             # Slice containing ids for artificial columns
             _UpperCAmelCase  :						Union[str, Any]							   =					slice(-self.n_art_vars - 1		,      -1 )

             # Delete the artificial variable columns
             _UpperCAmelCase  :						List[Any]							   =					np.delete(A		,      A		,      axis=1 )

             # Delete the objective row of the first stage
             _UpperCAmelCase  :						Union[str, Any]							   =					np.delete(A		,      0		,      axis=0 )

             _UpperCAmelCase  :						Any							   =					1
             self.n_rows -= 1
             _UpperCAmelCase  :						Dict							   =					0
             _UpperCAmelCase  :						List[str]							   =					False
             return tableau




      def   _A			( self		:       Optional[Any] ):
             # Stop simplex algorithm from cycling.
             for _ in range(100 ):
                    # Completion of each stage removes an objective. If both stages
                    # are complete, then no objectives are left
                    if not self.objectives:
                           _UpperCAmelCase  :						Any							   =					self.generate_col_titles(
                               self.n_vars		,      self.n_slack		,      self.n_art_vars )

                           # Find the values of each variable at optimal solution
                           return self.interpret_tableau(self.tableau		,      self.col_titles )

                    _UpperCAmelCase   ,						_UpperCAmelCase  :						List[str]							   =					self.find_pivot(self.tableau )

                    # If there are no more negative values in objective row
                    if self.stop_iter:
                           # Delete artificial variable columns and rows. Update attributes
                           _UpperCAmelCase  :						int							   =					self.change_stage(self.tableau )
                    else:
                           _UpperCAmelCase  :						Optional[Any]							   =					self.pivot(self.tableau		,      A		,      A )
             return {}





      def   _A			( self		:       List[Any]		,      A		:       np.ndarray		,      A		:       list[str] ):
             _UpperCAmelCase  :						str							   =					{"P": abs(tableau[0, -1] )}

             for i in range(self.n_vars ):
                    # Gives ids of nonzero entries in the ith column
                    _UpperCAmelCase  :						Dict							   =					np.nonzero(tableau[:, i] )
                    _UpperCAmelCase  :						Dict							   =					len(nonzero[0] )

                    # First entry in the nonzero ids
                    _UpperCAmelCase  :						str							   =					nonzero[0][0]
                    _UpperCAmelCase  :						str							   =					tableau[nonzero_rowidx, i]

                    # If there is only one nonzero value in column, which is one
                    if n_nonzero == nonzero_val == 1:
                           _UpperCAmelCase  :						Optional[Any]							   =					tableau[nonzero_rowidx, -1]
                           _UpperCAmelCase  :						Any							   =					rhs_val

        # Check for basic variables
             for title in col_titles:
                    # Don't add RHS or slack variables to output dict
                    if title[0] not in "R-s-a":
                           output_dict.setdefault(A		,      0 )
             return output_dict


if __name__ == "__main__":
  import doctest

  doctest.testmod()

