




'''simple docstring'''





from __future__ import annotations

import unittest
from collections.abc import Iterator






class 						lowercase     :






      def __init__(self ,  a__ ,  a__					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				str       						= label
         SCREAMING_SNAKE_CASE__			:				Any       						= parent
         SCREAMING_SNAKE_CASE__			:				Node | None       						= None
         SCREAMING_SNAKE_CASE__			:				Node | None       						= None






class 						lowercase     :






      def __init__(self					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Node | None       						= None






      def    A__(self					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Union[str, Any]       						= None






      def    A__(self					)       ->   bool:
         return self.root is None






      def    A__(self ,  a__					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Any       						= self._put(self.root ,  a__					)






      def    A__(self ,  a__ ,  a__ ,  a__ = None					)       ->   Node:
         if node is None:
            SCREAMING_SNAKE_CASE__			:				int       						= Node(a__ ,  a__					)
         else:
            if label < node.label:
               SCREAMING_SNAKE_CASE__			:				Optional[int]       						= self._put(node.left ,  a__ ,  a__					)
            elif label > node.label:
               SCREAMING_SNAKE_CASE__			:				List[str]       						= self._put(node.right ,  a__ ,  a__					)
            else:
               SCREAMING_SNAKE_CASE__			:				Optional[int]       						= f"""Node with label {label} already exists"""
               raise Exception(a__					)

         return node






      def    A__(self ,  a__					)       ->   Node:
         return self._search(self.root ,  a__					)






      def    A__(self ,  a__ ,  a__					)       ->   Node:
         if node is None:
            SCREAMING_SNAKE_CASE__			:				Any       						= f"""Node with label {label} does not exist"""
            raise Exception(a__					)
         else:
            if label < node.label:
               SCREAMING_SNAKE_CASE__			:				Tuple       						= self._search(node.left ,  a__					)
            elif label > node.label:
               SCREAMING_SNAKE_CASE__			:				Optional[int]       						= self._search(node.right ,  a__					)

         return node






      def    A__(self ,  a__					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Optional[int]       						= self.search(a__					)
         if node.right and node.left:
            SCREAMING_SNAKE_CASE__			:				Tuple       						= self._get_lowest_node(node.right					)
            SCREAMING_SNAKE_CASE__			:				Tuple       						= node.left
            SCREAMING_SNAKE_CASE__			:				Any       						= node.right
            SCREAMING_SNAKE_CASE__			:				Optional[Any]       						= lowest_node
            if node.right:
               SCREAMING_SNAKE_CASE__			:				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 ,  a__ ,  a__					)       ->   None:
         if new_children:
            SCREAMING_SNAKE_CASE__			:				List[Any]       						= node.parent

         if node.parent:
            if node.parent.right == node:
               SCREAMING_SNAKE_CASE__			:				Optional[int]       						= new_children
            else:
               SCREAMING_SNAKE_CASE__			:				Dict       						= new_children
         else:
            SCREAMING_SNAKE_CASE__			:				List[str]       						= new_children






      def    A__(self ,  a__					)       ->   Node:
         if node.left:
            SCREAMING_SNAKE_CASE__			:				int       						= self._get_lowest_node(node.left					)
         else:
            SCREAMING_SNAKE_CASE__			:				Tuple       						= node
            self._reassign_nodes(a__ ,  node.right					)

         return lowest_node






      def    A__(self ,  a__					)       ->   bool:
         try:
            self.search(a__					)
            return True
         except Exception:
            return False






      def    A__(self					)       ->   int:
         if self.root is None:
            raise Exception('''Binary search tree is empty'''					)

         SCREAMING_SNAKE_CASE__			:				List[str]       						= self.root
         while node.right is not None:
            SCREAMING_SNAKE_CASE__			:				Optional[int]       						= node.right

         return node.label






      def    A__(self					)       ->   int:
         if self.root is None:
            raise Exception('''Binary search tree is empty'''					)

         SCREAMING_SNAKE_CASE__			:				Tuple       						= self.root
         while node.left is not None:
            SCREAMING_SNAKE_CASE__			:				Any       						= node.left

         return node.label






      def    A__(self					)       ->   Iterator[Node]:
         return self._inorder_traversal(self.root					)






      def    A__(self ,  a__					)       ->   Iterator[Node]:
         if node is not None:
            yield from self._inorder_traversal(node.left					)
            yield node
            yield from self._inorder_traversal(node.right					)






      def    A__(self					)       ->   Iterator[Node]:
         return self._preorder_traversal(self.root					)






      def    A__(self ,  a__					)       ->   Iterator[Node]:
         if node is not None:
            yield node
            yield from self._preorder_traversal(node.left					)
            yield from self._preorder_traversal(node.right					)






class 						lowercase     (   unittest.TestCase):






      @staticmethod
      def    A__()       ->   BinarySearchTree:
         SCREAMING_SNAKE_CASE__			:				Dict       						= 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    A__(self					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Optional[int]       						= 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(a__					):  # noqa: B017
            t.put(1					)






      def    A__(self					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Optional[int]       						= self._get_binary_search_tree()

         SCREAMING_SNAKE_CASE__			:				str       						= t.search(6					)
         assert node.label == 6

         SCREAMING_SNAKE_CASE__			:				Optional[Any]       						= t.search(1_3					)
         assert node.label == 1_3

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






      def    A__(self					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Tuple       						= 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    A__(self					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				int       						= 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					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Optional[Any]       						= self._get_binary_search_tree()
         t.empty()
         assert t.root is None






      def    A__(self					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				str       						= self._get_binary_search_tree()
         assert not t.is_empty()

         t.empty()
         assert t.is_empty()






      def    A__(self					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Dict       						= self._get_binary_search_tree()

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






      def    A__(self					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Tuple       						= self._get_binary_search_tree()

         assert t.get_max_label() == 1_4

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






      def    A__(self					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Dict       						= 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					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Tuple       						= self._get_binary_search_tree()

         SCREAMING_SNAKE_CASE__			:				Any       						= [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    A__(self					)       ->   None:
         SCREAMING_SNAKE_CASE__			:				Dict       						= self._get_binary_search_tree()

         SCREAMING_SNAKE_CASE__			:				Optional[int]       						= [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 				UpperCamelCase	(  ):




   '''simple docstring'''

   SCREAMING_SNAKE_CASE__			:				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   )

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

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

   # Prints all the elements of the list in preorder traversal
   SCREAMING_SNAKE_CASE__			:				List[str]       						= [i.label for i in t.preorder_traversal()]
   print('''Preorder traversal:'''	,     snake_case   )

   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(
       '''
          4
         / \\
        1   7
             \\
              5
        '''   )
   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
   SCREAMING_SNAKE_CASE__			:				int       						= [i.label for i in t.inorder_traversal()]
   print('''Inorder traversal after delete:'''	,     snake_case   )

   # Prints all the elements of the list in preorder traversal after delete
   SCREAMING_SNAKE_CASE__			:				int       						= [i.label for i in t.preorder_traversal()]
   print('''Preorder traversal after delete:'''	,     snake_case   )

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


if __name__ == "__main__":
       binary_search_tree_example()







'''simple docstring'''





import argparse
import json
import re
import string
import sys
from collections import Counter


def 				UpperCamelCase	(  snake_case   ):




   '''simple docstring'''

   def remove_articles(snake_case   ):
      return re.sub(R'''\b(a|an|the)\b'''	,     ''' '''	,     snake_case   )

   def white_space_fix(snake_case   ):
      return " ".join(text.split()   )

   def remove_punc(snake_case   ):
      SCREAMING_SNAKE_CASE__			:				Optional[int]       						= set(string.punctuation   )
      return "".join(ch for ch in text if ch not in exclude   )

   def lower(snake_case   ):
      return text.lower()

   return white_space_fix(remove_articles(remove_punc(lower(snake_case   )   )   )   )


def 				UpperCamelCase	(  snake_case	,     snake_case   ):




   '''simple docstring'''

   SCREAMING_SNAKE_CASE__			:				Tuple       						= normalize_answer(snake_case   ).split()
   SCREAMING_SNAKE_CASE__			:				List[Any]       						= normalize_answer(snake_case   ).split()
   SCREAMING_SNAKE_CASE__			:				Dict       						= Counter(snake_case   ) & Counter(snake_case   )
   SCREAMING_SNAKE_CASE__			:				int       						= sum(common.values()   )
   if num_same == 0:
      return 0
   SCREAMING_SNAKE_CASE__			:				Tuple       						= 1.0 * num_same / len(snake_case   )
   SCREAMING_SNAKE_CASE__			:				Tuple       						= 1.0 * num_same / len(snake_case   )
   SCREAMING_SNAKE_CASE__			:				Optional[Any]       						= (2 * precision * recall) / (precision + recall)
   return fa


def 				UpperCamelCase	(  snake_case	,     snake_case   ):




   '''simple docstring'''

   return normalize_answer(snake_case   ) == normalize_answer(snake_case   )


def 				UpperCamelCase	(  snake_case	,     snake_case	,     snake_case   ):




   '''simple docstring'''

   SCREAMING_SNAKE_CASE__			:				Any       						= []
   for ground_truth in ground_truths:
      SCREAMING_SNAKE_CASE__			:				List[Any]       						= metric_fn(snake_case	,     snake_case   )
      scores_for_ground_truths.append(snake_case   )
   return max(snake_case   )


def 				UpperCamelCase	(  snake_case	,     snake_case   ):




   '''simple docstring'''

   SCREAMING_SNAKE_CASE__			:				str       						= 0
   SCREAMING_SNAKE_CASE__			:				Optional[int]       						= []
   for passage in dataset:
      for qa in passage["qas"]:
         total += 1
         if qa["id"] not in predictions:
            SCREAMING_SNAKE_CASE__			:				Any       						= f"""Unanswered question {qa["id"]} will receive score 0."""
            print(snake_case	,     file=sys.stderr   )
            continue

         SCREAMING_SNAKE_CASE__			:				Union[str, Any]       						= [x['''text'''] for x in qa['''answers''']]
         SCREAMING_SNAKE_CASE__			:				Optional[int]       						= predictions[qa['''id''']]

         SCREAMING_SNAKE_CASE__			:				List[str]       						= metric_max_over_ground_truths(snake_case	,     snake_case	,     snake_case   )
         if int(_exact_match   ) == 1:
            correct_ids.append(qa['''id''']   )
         exact_match += _exact_match

         fa += metric_max_over_ground_truths(snake_case	,     snake_case	,     snake_case   )

   SCREAMING_SNAKE_CASE__			:				int       						= exact_match / total
   SCREAMING_SNAKE_CASE__			:				Optional[int]       						= fa / total

   return {"exact_match": exact_match, "f1": fa}, correct_ids


if __name__ == "__main__":
       lowercase__			=	'''1.0'''
       lowercase__			=	argparse.ArgumentParser('''Official evaluation script for ReCoRD v1.0.''')
       parser.add_argument('''data_file''', help='''The dataset file in JSON format.''')
       parser.add_argument('''pred_file''', help='''The model prediction file in JSON format.''')
       parser.add_argument('''--output_correct_ids''', action='''store_true''', help='''Output the correctly answered query IDs.''')
       lowercase__			=	parser.parse_args()

       with open(args.data_file) as data_file:
              lowercase__			=	json.load(data_file)
              if dataset_json["version"] != expected_version:
                     print(
                         F"Evaluation expects v-{expected_version}, but got dataset with v-{dataset_json['version']}",
                         file=sys.stderr,
                     )
              lowercase__			=	dataset_json['''data''']

       with open(args.pred_file) as pred_file:
              lowercase__			=	json.load(pred_file)

       lowercase__	,     lowercase__			=	evaluate(dataset, predictions)

       if args.output_correct_ids:
              print(F"Output {len(correct_ids)} correctly answered question IDs.")
              with open('''correct_ids.json''', '''w''') as f:
                     json.dump(correct_ids, f)

