

from __future__ import annotations

from random import random
from typing import Generic, TypeVar

_SCREAMING_SNAKE_CASE  :						Optional[Any]         =    TypeVar('''KT''')
_SCREAMING_SNAKE_CASE  :						List[str]         =    TypeVar('''VT''')






class  UpperCAmelCase__	( Generic[KT, VT] ):






  """simple docstring"""


  def __init__(							self		:	List[Any]			,     __lowerCamelCase		:	KT | str = "root"			,     __lowerCamelCase		:	VT | None = None      )	->							int:
       SCREAMING_SNAKE_CASE__					=					key
       SCREAMING_SNAKE_CASE__					=					value
       SCREAMING_SNAKE_CASE__					=					[]






  def __repr__(							self		:	Optional[int]      )	->							str:
       return f'''Node({self.key}: {self.value})'''







  @property
  def    lowercase_	(							self		:	int      )	->							int:
       return len(self.forward      )






class  UpperCAmelCase__	( Generic[KT, VT] ):






  """simple docstring"""


  def __init__(							self		:	Tuple			,     __lowerCamelCase		:	float = 0.5			,     __lowerCamelCase		:	int = 16      )	->							int:
       SCREAMING_SNAKE_CASE__					=					Node[KT, VT]()
       SCREAMING_SNAKE_CASE__					=					0
       SCREAMING_SNAKE_CASE__					=					p
       SCREAMING_SNAKE_CASE__					=					max_level






  def __str__(							self		:	Optional[int]      )	->							str:
       SCREAMING_SNAKE_CASE__					=					list(self      )

       if len(__lowerCamelCase      ) == 0:
            return f'''SkipList(level={self.level})'''

       SCREAMING_SNAKE_CASE__					=					max((len(str(__lowerCamelCase      )      ) for item in items)			,     default=4      )
       SCREAMING_SNAKE_CASE__					=					max(__lowerCamelCase			,     4      ) + 4

       SCREAMING_SNAKE_CASE__					=					self.head
       SCREAMING_SNAKE_CASE__					=					[]

       SCREAMING_SNAKE_CASE__					=					node.forward.copy()
       lines.append(f'''[{node.key}]'''.ljust(__lowerCamelCase			,     '''-'''      ) + '''* ''' * len(__lowerCamelCase      )      )
       lines.append(''' ''' * label_size + '''| ''' * len(__lowerCamelCase      )      )

       while len(node.forward      ) != 0:
            SCREAMING_SNAKE_CASE__					=					node.forward[0]

            lines.append(
                f'''[{node.key}]'''.ljust(__lowerCamelCase			,     '''-'''      )
                + ''' '''.join(str(n.key      ) if n.key == node.key else '''|''' for n in forwards      )      )
            lines.append(''' ''' * label_size + '''| ''' * len(__lowerCamelCase      )      )
            SCREAMING_SNAKE_CASE__					=					node.forward

       lines.append('''None'''.ljust(__lowerCamelCase      ) + '''* ''' * len(__lowerCamelCase      )      )
       return f'''SkipList(level={self.level})\n''' + "\n".join(__lowerCamelCase      )






  def __iter__(							self		:	Any      )	->							List[str]:
       SCREAMING_SNAKE_CASE__					=					self.head

       while len(node.forward      ) != 0:
            yield node.forward[0].key
            SCREAMING_SNAKE_CASE__					=					node.forward[0]






  def    lowercase_	(							self		:	List[Any]      )	->							int:
       SCREAMING_SNAKE_CASE__					=					1
       while random() < self.p and level < self.max_level:
            level += 1

       return level






  def    lowercase_	(							self		:	Optional[int]			,     __lowerCamelCase		:	int      )	->							tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:
       SCREAMING_SNAKE_CASE__					=					[]

       SCREAMING_SNAKE_CASE__					=					self.head

       for i in reversed(range(self.level      )      ):
            # i < node.level - When node level is lesser than `i` decrement `i`.
            # node.forward[i].key < key - Jumping to node with key value higher
            #                             or equal to searched key would result
            #                             in skipping searched key.
            while i < node.level and node.forward[i].key < key:
                 SCREAMING_SNAKE_CASE__					=					node.forward[i]
            # Each leftmost node (relative to searched node) will potentially have to
            # be updated.
            update_vector.append(__lowerCamelCase      )

       update_vector.reverse()  # Note that we were inserting values in reverse order.

       # len(node.forward) != 0 - If current node doesn't contain any further
       #                          references then searched key is not present.
       # node.forward[0].key == key - Next node key should be equal to search key
       #                              if key is present.
       if len(node.forward      ) != 0 and node.forward[0].key == key:
            return node.forward[0], update_vector
       else:
            return None, update_vector






  def    lowercase_	(							self		:	List[Any]			,     __lowerCamelCase		:	KT      )	->							str:
       SCREAMING_SNAKE_CASE__,SCREAMING_SNAKE_CASE__					=					self._locate_node(__lowerCamelCase      )

       if node is not None:
            for i, update_node in enumerate(__lowerCamelCase      ):
                 # Remove or replace all references to removed node.
                 if update_node.level > i and update_node.forward[i].key == key:
                      if node.level > i:
                           SCREAMING_SNAKE_CASE__					=					node.forward[i]
                      else:
                           SCREAMING_SNAKE_CASE__					=					update_node.forward[:i]






  def    lowercase_	(							self		:	Tuple			,     __lowerCamelCase		:	KT			,     __lowerCamelCase		:	VT      )	->							Tuple:
       SCREAMING_SNAKE_CASE__,SCREAMING_SNAKE_CASE__					=					self._locate_node(__lowerCamelCase      )
       if node is not None:
            SCREAMING_SNAKE_CASE__					=					value
       else:
            SCREAMING_SNAKE_CASE__					=					self.random_level()

            if level > self.level:
                 # After level increase we have to add additional nodes to head.
                 for _ in range(self.level - 1			,     __lowerCamelCase      ):
                      update_vector.append(self.head      )
                 SCREAMING_SNAKE_CASE__					=					level

            SCREAMING_SNAKE_CASE__					=					Node(__lowerCamelCase			,     __lowerCamelCase      )

            for i, update_node in enumerate(update_vector[:level]      ):
                 # Change references to pass through new node.
                 if update_node.level > i:
                      new_node.forward.append(update_node.forward[i]      )

                 if update_node.level < i + 1:
                      update_node.forward.append(__lowerCamelCase      )
                 else:
                      SCREAMING_SNAKE_CASE__					=					new_node







  def    lowercase_	(							self		:	Optional[int]			,     __lowerCamelCase		:	VT      )	->							VT | None:
       SCREAMING_SNAKE_CASE__,SCREAMING_SNAKE_CASE__					=					self._locate_node(__lowerCamelCase      )

       if node is not None:
            return node.value

       return None



def        UpperCAmelCase_     (		):





     '''simple docstring'''




     SCREAMING_SNAKE_CASE__					=					SkipList()
     skip_list.insert('''Key1'''   ,	3       )
     skip_list.insert('''Key2'''   ,	12       )
     skip_list.insert('''Key3'''   ,	41       )
     skip_list.insert('''Key4'''   ,	-19       )

     SCREAMING_SNAKE_CASE__					=					skip_list.head
     SCREAMING_SNAKE_CASE__					=					{}
     while node.level != 0:
          SCREAMING_SNAKE_CASE__					=					node.forward[0]
          SCREAMING_SNAKE_CASE__					=					node.value

     assert len(_A       ) == 4
     assert all_values["Key1"] == 3
     assert all_values["Key2"] == 12
     assert all_values["Key3"] == 41
     assert all_values["Key4"] == -19
def        UpperCAmelCase_     (		):





     '''simple docstring'''




     SCREAMING_SNAKE_CASE__					=					SkipList()
     skip_list.insert('''Key1'''   ,	10       )
     skip_list.insert('''Key1'''   ,	12       )

     skip_list.insert('''Key5'''   ,	7       )
     skip_list.insert('''Key7'''   ,	10       )
     skip_list.insert('''Key10'''   ,	5       )

     skip_list.insert('''Key7'''   ,	7       )
     skip_list.insert('''Key5'''   ,	5       )
     skip_list.insert('''Key10'''   ,	10       )

     SCREAMING_SNAKE_CASE__					=					skip_list.head
     SCREAMING_SNAKE_CASE__					=					{}
     while node.level != 0:
          SCREAMING_SNAKE_CASE__					=					node.forward[0]
          SCREAMING_SNAKE_CASE__					=					node.value

     if len(_A       ) != 4:
          print()
     assert len(_A       ) == 4
     assert all_values["Key1"] == 12
     assert all_values["Key7"] == 7
     assert all_values["Key5"] == 5
     assert all_values["Key10"] == 10
def        UpperCAmelCase_     (		):





     '''simple docstring'''




     SCREAMING_SNAKE_CASE__					=					SkipList()
     assert skip_list.find('''Some key'''       ) is None
def        UpperCAmelCase_     (		):





     '''simple docstring'''




     SCREAMING_SNAKE_CASE__					=					SkipList()

     skip_list.insert('''Key2'''   ,	20       )
     assert skip_list.find('''Key2'''       ) == 20

     skip_list.insert('''Some Key'''   ,	10       )
     skip_list.insert('''Key2'''   ,	8       )
     skip_list.insert('''V'''   ,	13       )

     assert skip_list.find('''Y'''       ) is None
     assert skip_list.find('''Key2'''       ) == 8
     assert skip_list.find('''Some Key'''       ) == 10
     assert skip_list.find('''V'''       ) == 13
def        UpperCAmelCase_     (		):





     '''simple docstring'''




     SCREAMING_SNAKE_CASE__					=					SkipList()
     skip_list.delete('''Some key'''       )

     assert len(skip_list.head.forward       ) == 0
def        UpperCAmelCase_     (		):





     '''simple docstring'''




     SCREAMING_SNAKE_CASE__					=					SkipList()

     skip_list.insert('''Key1'''   ,	12       )
     skip_list.insert('''V'''   ,	13       )
     skip_list.insert('''X'''   ,	14       )
     skip_list.insert('''Key2'''   ,	15       )

     skip_list.delete('''V'''       )
     skip_list.delete('''Key2'''       )

     assert skip_list.find('''V'''       ) is None
     assert skip_list.find('''Key2'''       ) is None
def        UpperCAmelCase_     (		):





     '''simple docstring'''




     SCREAMING_SNAKE_CASE__					=					SkipList()

     skip_list.insert('''Key1'''   ,	12       )
     skip_list.insert('''V'''   ,	13       )
     skip_list.insert('''X'''   ,	14       )
     skip_list.insert('''Key2'''   ,	15       )

     skip_list.delete('''V'''       )
     assert skip_list.find('''V'''       ) is None
     assert skip_list.find('''X'''       ) == 14
     assert skip_list.find('''Key1'''       ) == 12
     assert skip_list.find('''Key2'''       ) == 15

     skip_list.delete('''X'''       )
     assert skip_list.find('''V'''       ) is None
     assert skip_list.find('''X'''       ) is None
     assert skip_list.find('''Key1'''       ) == 12
     assert skip_list.find('''Key2'''       ) == 15

     skip_list.delete('''Key1'''       )
     assert skip_list.find('''V'''       ) is None
     assert skip_list.find('''X'''       ) is None
     assert skip_list.find('''Key1'''       ) is None
     assert skip_list.find('''Key2'''       ) == 15

     skip_list.delete('''Key2'''       )
     assert skip_list.find('''V'''       ) is None
     assert skip_list.find('''X'''       ) is None
     assert skip_list.find('''Key1'''       ) is None
     assert skip_list.find('''Key2'''       ) is None
def        UpperCAmelCase_     (		):





     '''simple docstring'''




     SCREAMING_SNAKE_CASE__					=					SkipList()

     skip_list.insert('''Key1'''   ,	12       )
     skip_list.insert('''V'''   ,	13       )
     skip_list.insert('''X'''   ,	1_42       )
     skip_list.insert('''Key2'''   ,	15       )

     skip_list.delete('''X'''       )

     def traverse_keys(_A       ):
          yield node.key
          for forward_node in node.forward:
               yield from traverse_keys(_A       )

     assert len(set(traverse_keys(skip_list.head       )       )       ) == 4
def        UpperCAmelCase_     (		):





     '''simple docstring'''




     def is_sorted(_A       ):
          return all(next_item >= item for item, next_item in zip(_A   ,	lst[1:]       )       )

     SCREAMING_SNAKE_CASE__					=					SkipList()
     for i in range(10       ):
          skip_list.insert(_A   ,	_A       )
     assert is_sorted(list(_A       )       )
     skip_list.delete(5       )
     skip_list.delete(8       )
     skip_list.delete(2       )
     assert is_sorted(list(_A       )       )
     skip_list.insert(-12   ,	-12       )
     skip_list.insert(77   ,	77       )
     assert is_sorted(list(_A       )       )
def        UpperCAmelCase_     (		):





     '''simple docstring'''




     for _ in range(1_00       ):
          # Repeat test 100 times due to the probabilistic nature of skip list
          # random values == random bugs
          test_insert()
          test_insert_overrides_existing_value()

          test_searching_empty_list_returns_none()
          test_search()

          test_deleting_item_from_empty_list_do_nothing()
          test_deleted_items_are_not_founded_by_find_method()
          test_delete_removes_only_given_key()
          test_delete_doesnt_leave_dead_nodes()

          test_iter_always_yields_sorted_values()
def        UpperCAmelCase_     (		):





     '''simple docstring'''




     SCREAMING_SNAKE_CASE__					=					SkipList()
     skip_list.insert(2   ,	'''2'''       )
     skip_list.insert(4   ,	'''4'''       )
     skip_list.insert(6   ,	'''4'''       )
     skip_list.insert(4   ,	'''5'''       )
     skip_list.insert(8   ,	'''4'''       )
     skip_list.insert(9   ,	'''4'''       )

     skip_list.delete(4       )

     print(_A       )


if __name__ == "__main__":
       import doctest

       doctest.testmod()
       main()





import math
import time

from transformers import Trainer, is_torch_tpu_available
from transformers.trainer_utils import PredictionOutput, speed_metrics


if is_torch_tpu_available(check_device=False):
       import torch_xla.core.xla_model as xm
       import torch_xla.debug.metrics as met






class  UpperCAmelCase__	( A__ ):






  """simple docstring"""


  def __init__(							self		:	Tuple			,     *__lowerCamelCase		:	List[str]			,     __lowerCamelCase		:	Any=None			,     __lowerCamelCase		:	Optional[int]=None			,     **__lowerCamelCase		:	Optional[int]      )	->							List[str]:
       super().__init__(*__lowerCamelCase			,     **__lowerCamelCase      )
       SCREAMING_SNAKE_CASE__					=					eval_examples
       SCREAMING_SNAKE_CASE__					=					post_process_function






  def    lowercase_	(							self		:	Optional[Any]			,     __lowerCamelCase		:	Dict=None			,     __lowerCamelCase		:	int=None			,     __lowerCamelCase		:	str=None			,     __lowerCamelCase		:	str = "eval"      )	->							Optional[Any]:
       SCREAMING_SNAKE_CASE__					=					self.eval_dataset if eval_dataset is None else eval_dataset
       SCREAMING_SNAKE_CASE__					=					self.get_eval_dataloader(__lowerCamelCase      )
       SCREAMING_SNAKE_CASE__					=					self.eval_examples if eval_examples is None else eval_examples

       # Temporarily disable metric computation, we will do it in the loop here.
       SCREAMING_SNAKE_CASE__					=					self.compute_metrics
       SCREAMING_SNAKE_CASE__					=					None
       SCREAMING_SNAKE_CASE__					=					self.prediction_loop if self.args.use_legacy_prediction_loop else self.evaluation_loop
       SCREAMING_SNAKE_CASE__					=					time.time()
       try:
            SCREAMING_SNAKE_CASE__					=					eval_loop(
                __lowerCamelCase			,     description='''Evaluation'''			,     prediction_loss_only=True if compute_metrics is None else None			,     ignore_keys=__lowerCamelCase			,     metric_key_prefix=__lowerCamelCase			,     )
       finally:
            SCREAMING_SNAKE_CASE__					=					compute_metrics
       SCREAMING_SNAKE_CASE__					=					self.args.eval_batch_size * self.args.world_size
       if f'''{metric_key_prefix}_jit_compilation_time''' in output.metrics:
            start_time += output.metrics[f'''{metric_key_prefix}_jit_compilation_time''']
       output.metrics.update(
           speed_metrics(
               __lowerCamelCase			,     __lowerCamelCase			,     num_samples=output.num_samples			,     num_steps=math.ceil(output.num_samples / total_batch_size      )			,     )      )
       if self.post_process_function is not None and self.compute_metrics is not None and self.args.should_save:
            # Only the main node write the results by default
            SCREAMING_SNAKE_CASE__					=					self.post_process_function(__lowerCamelCase			,     __lowerCamelCase			,     output.predictions      )
            SCREAMING_SNAKE_CASE__					=					self.compute_metrics(__lowerCamelCase      )

            # Prefix all keys with metric_key_prefix + '_'
            for key in list(metrics.keys()      ):
                 if not key.startswith(f'''{metric_key_prefix}_'''      ):
                      SCREAMING_SNAKE_CASE__					=					metrics.pop(__lowerCamelCase      )
            metrics.update(output.metrics      )
       else:
            SCREAMING_SNAKE_CASE__					=					output.metrics

       if self.args.should_log:
            # Only the main node log the results by default
            self.log(__lowerCamelCase      )

       if self.args.tpu_metrics_debug or self.args.debug:
            # tpu-comment: Logging debug metrics for PyTorch/XLA (compile, execute times, ops, etc.)
            xm.master_print(met.metrics_report()      )

       SCREAMING_SNAKE_CASE__					=					self.callback_handler.on_evaluate(self.args			,     self.state			,     self.control			,     __lowerCamelCase      )
       return metrics







  def    lowercase_	(							self		:	Dict			,     __lowerCamelCase		:	Dict			,     __lowerCamelCase		:	str			,     __lowerCamelCase		:	str=None			,     __lowerCamelCase		:	str = "test"      )	->							Any:
       SCREAMING_SNAKE_CASE__					=					self.get_test_dataloader(__lowerCamelCase      )

       # Temporarily disable metric computation, we will do it in the loop here.
       SCREAMING_SNAKE_CASE__					=					self.compute_metrics
       SCREAMING_SNAKE_CASE__					=					None
       SCREAMING_SNAKE_CASE__					=					self.prediction_loop if self.args.use_legacy_prediction_loop else self.evaluation_loop
       SCREAMING_SNAKE_CASE__					=					time.time()
       try:
            SCREAMING_SNAKE_CASE__					=					eval_loop(
                __lowerCamelCase			,     description='''Prediction'''			,     prediction_loss_only=True if compute_metrics is None else None			,     ignore_keys=__lowerCamelCase			,     metric_key_prefix=__lowerCamelCase			,     )
       finally:
            SCREAMING_SNAKE_CASE__					=					compute_metrics
       SCREAMING_SNAKE_CASE__					=					self.args.eval_batch_size * self.args.world_size
       if f'''{metric_key_prefix}_jit_compilation_time''' in output.metrics:
            start_time += output.metrics[f'''{metric_key_prefix}_jit_compilation_time''']
       output.metrics.update(
           speed_metrics(
               __lowerCamelCase			,     __lowerCamelCase			,     num_samples=output.num_samples			,     num_steps=math.ceil(output.num_samples / total_batch_size      )			,     )      )

       if self.post_process_function is None or self.compute_metrics is None:
            return output

       SCREAMING_SNAKE_CASE__					=					self.post_process_function(__lowerCamelCase			,     __lowerCamelCase			,     output.predictions			,     '''predict'''      )
       SCREAMING_SNAKE_CASE__					=					self.compute_metrics(__lowerCamelCase      )

       # Prefix all keys with metric_key_prefix + '_'
       for key in list(metrics.keys()      ):
            if not key.startswith(f'''{metric_key_prefix}_'''      ):
                 SCREAMING_SNAKE_CASE__					=					metrics.pop(__lowerCamelCase      )
       metrics.update(output.metrics      )
       return PredictionOutput(predictions=predictions.predictions			,     label_ids=predictions.label_ids			,     metrics=__lowerCamelCase      )


