"""simple docstring"""


from __future__ import annotations

from random import random
from typing import Generic, TypeVar

UpperCAmelCase__  		=						TypeVar("""KT""")
UpperCAmelCase__  		=						TypeVar("""VT""")


class        a				(		Generic[KT, VT]   ):


    def __init__(					self	:  Dict   ,				__lowerCAmelCase	:  KT | str = "root"   ,				__lowerCAmelCase	:  VT | None = None					):
      _UpperCAmelCase						 =      key
      _UpperCAmelCase						 =      value
      _UpperCAmelCase						 =      []


    def __repr__(					self	:  List[Any]					):
      return f'''Node({self.key}: {self.value})'''


    @property
    def      lowerCAmelCase_  (					self	:  Optional[Any]					):
      return len(self.forward					)



class        a				(		Generic[KT, VT]   ):


    def __init__(					self	:  Dict   ,				__lowerCAmelCase	:  float = 0.5   ,				__lowerCAmelCase	:  int = 16					):
      _UpperCAmelCase						 =      Node[KT, VT]()
      _UpperCAmelCase						 =      0
      _UpperCAmelCase						 =      p
      _UpperCAmelCase						 =      max_level


    def __str__(					self	:  str					):
      _UpperCAmelCase						 =      list(self					)

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

      _UpperCAmelCase						 =      max((len(str(__lowerCAmelCase					)					) for item in items)   ,				default=4					)
      _UpperCAmelCase						 =      max(__lowerCAmelCase   ,				4					) + 4

      _UpperCAmelCase						 =      self.head
      _UpperCAmelCase						 =      []

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

      while len(node.forward					) != 0:
        _UpperCAmelCase						 =      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					)					)
        _UpperCAmelCase						 =      node.forward

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


    def __iter__(					self	:  Union[str, Any]					):
      _UpperCAmelCase						 =      self.head

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


    def      lowerCAmelCase_  (					self	:  Union[str, Any]					):
      _UpperCAmelCase						 =      1
      while random() < self.p and level < self.max_level:
        level += 1

      return level


    def      lowerCAmelCase_  (					self	:  str   ,				__lowerCAmelCase	:  List[str]					):
      _UpperCAmelCase						 =      []

      _UpperCAmelCase						 =      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:
          _UpperCAmelCase						 =      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      lowerCAmelCase_  (					self	:  Tuple   ,				__lowerCAmelCase	:  KT					):
      _UpperCAmelCase ,				_UpperCAmelCase						 =      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:
              _UpperCAmelCase						 =      node.forward[i]
            else:
              _UpperCAmelCase						 =      update_node.forward[:i]


    def      lowerCAmelCase_  (					self	:  int   ,				__lowerCAmelCase	:  KT   ,				__lowerCAmelCase	:  VT					):
      _UpperCAmelCase ,				_UpperCAmelCase						 =      self._locate_node(__lowerCAmelCase					)
      if node is not None:
        _UpperCAmelCase						 =      value
      else:
        _UpperCAmelCase						 =      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					)
          _UpperCAmelCase						 =      level

        _UpperCAmelCase						 =      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:
            _UpperCAmelCase						 =      new_node


    def      lowerCAmelCase_  (					self	:  Any   ,				__lowerCAmelCase	:  VT					):
      _UpperCAmelCase ,				_UpperCAmelCase						 =      self._locate_node(__lowerCAmelCase					)

      if node is not None:
        return node.value

      return None






def     __UpperCAmelCase					(			):







  """simple docstring"""
  _UpperCAmelCase						 =      SkipList()
  skip_list.insert("""Key1"""   ,3		)
  skip_list.insert("""Key2"""   ,12		)
  skip_list.insert("""Key3"""   ,41		)
  skip_list.insert("""Key4"""   ,-19		)

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

  assert len(lowercase		) == 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"""
  _UpperCAmelCase						 =      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		)

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

  if len(lowercase		) != 4:
    print()
  assert len(lowercase		) == 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"""
  _UpperCAmelCase						 =      SkipList()
  assert skip_list.find("""Some key"""		) is None






def     __UpperCAmelCase					(			):







  """simple docstring"""
  _UpperCAmelCase						 =      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"""
  _UpperCAmelCase						 =      SkipList()
  skip_list.delete("""Some key"""		)

  assert len(skip_list.head.forward		) == 0






def     __UpperCAmelCase					(			):







  """simple docstring"""
  _UpperCAmelCase						 =      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"""
  _UpperCAmelCase						 =      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"""
  _UpperCAmelCase						 =      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(lowercase		):
    yield node.key
    for forward_node in node.forward:
      yield from traverse_keys(lowercase		)

  assert len(set(traverse_keys(skip_list.head		)		)		) == 4






def     __UpperCAmelCase					(			):







  """simple docstring"""
  def is_sorted(lowercase		):
    return all(next_item >= item for item, next_item in zip(lowercase   ,lst[1:]		)		)

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






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"""
  _UpperCAmelCase						 =      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(lowercase		)


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    main()

"""simple docstring"""


import datasets


UpperCAmelCase__  		=						"""\
@InProceedings{conneau2018xnli,
  author = \"Conneau, Alexis
                 and Rinott, Ruty
                 and Lample, Guillaume
                 and Williams, Adina
                 and Bowman, Samuel R.
                 and Schwenk, Holger
                 and Stoyanov, Veselin\",
  title = \"XNLI: Evaluating Cross-lingual Sentence Representations\",
  booktitle = \"Proceedings of the 2018 Conference on Empirical Methods
               in Natural Language Processing\",
  year = \"2018\",
  publisher = \"Association for Computational Linguistics\",
  location = \"Brussels, Belgium\",
}
"""

UpperCAmelCase__  		=						"""\
XNLI is a subset of a few thousand examples from MNLI which has been translated
into a 14 different languages (some low-ish resource). As with MNLI, the goal is
to predict textual entailment (does sentence A imply/contradict/neither sentence
B) and is a classification task (given two sentences, predict one of three
labels).
"""

UpperCAmelCase__  		=						"""
Computes XNLI score which is just simple accuracy.
Args:
    predictions: Predicted labels.
    references: Ground truth labels.
Returns:
    'accuracy': accuracy
Examples:

    >>> predictions = [0, 1]
    >>> references = [0, 1]
    >>> xnli_metric = datasets.load_metric(\"xnli\")
    >>> results = xnli_metric.compute(predictions=predictions, references=references)
    >>> print(results)
    {'accuracy': 1.0}
"""






def     __UpperCAmelCase					(			lowercase   ,lowercase		):







  """simple docstring"""
  return (preds == labels).mean()


@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION	,							_KWARGS_DESCRIPTION   )
class        a				(		datasets.Metric   ):


    def      lowerCAmelCase_  (					self	:  Union[str, Any]					):
      return datasets.MetricInfo(
          description=_DESCRIPTION   ,				citation=_CITATION   ,				inputs_description=_KWARGS_DESCRIPTION   ,				features=datasets.Features(
              {
                  """predictions""": datasets.Value("""int64""" if self.config_name != """sts-b""" else """float32"""					),
                  """references""": datasets.Value("""int64""" if self.config_name != """sts-b""" else """float32"""					),
              }					)   ,				codebase_urls=[]   ,				reference_urls=[]   ,				format="""numpy"""   ,				)


    def      lowerCAmelCase_  (					self	:  List[str]   ,				__lowerCAmelCase	:  int   ,				__lowerCAmelCase	:  Any					):
      return {"accuracy": simple_accuracy(__lowerCAmelCase   ,				__lowerCAmelCase					)}
