"""simple docstring"""




from __future__ import annotations

from random import random
from typing import Generic, TypeVar

__lowerCAmelCase     :				Dict    				=    TypeVar("KT")
__lowerCAmelCase     :				Optional[Any]    				=    TypeVar("VT")

class    a_   (  Generic[KT, VT]      ):




					def __init__(						self    :  Tuple	,    snake_case__    :  KT | str = "root"	,    snake_case__    :  VT | None = None  ):
							lowerCAmelCase__   = key
							lowerCAmelCase__   = value
							lowerCAmelCase__   = []




					def __repr__(						self    :  Union[str, Any]  ):
							return F"""Node({self.key}: {self.value})"""




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

class    a_   (  Generic[KT, VT]      ):




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




					def __str__(						self    :  int  ):
							lowerCAmelCase__   = list(self  )

							if len(snake_case__  ) == 0:
									return F"""SkipList(level={self.level})"""

							lowerCAmelCase__   = max((len(str(snake_case__  )  ) for item in items)	,    default=4  )
							lowerCAmelCase__   = max(snake_case__	,    4  ) + 4

							lowerCAmelCase__   = self.head
							lowerCAmelCase__   = []

							lowerCAmelCase__   = node.forward.copy()
							lines.append(F"""[{node.key}]""".ljust(snake_case__	,    """-"""  ) + """* """ * len(snake_case__  )  )
							lines.append(""" """ * label_size + """| """ * len(snake_case__  )  )

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

									lines.append(
									    F"""[{node.key}]""".ljust(snake_case__	,    """-"""  )
									    + """ """.join(str(n.key  ) if n.key == node.key else """|""" for n in forwards  )  )
									lines.append(""" """ * label_size + """| """ * len(snake_case__  )  )
									lowerCAmelCase__   = node.forward

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




					def __iter__(						self    :  Any  ):
							lowerCAmelCase__   = self.head

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




					def     _SCREAMING_SNAKE_CASE    (						self    :  Dict  ):
							lowerCAmelCase__   = 1
							while random() < self.p and level < self.max_level:
									level += 1

							return level




					def     _SCREAMING_SNAKE_CASE    (						self    :  List[str]	,    snake_case__    :  List[str]  ):
							lowerCAmelCase__   = []

							lowerCAmelCase__   = 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:
											lowerCAmelCase__   = node.forward[i]
									# Each leftmost node (relative to searched node) will potentially have to
									# be updated.
									update_vector.append(snake_case__  )

							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     _SCREAMING_SNAKE_CASE    (						self    :  List[str]	,    snake_case__    :  KT  ):
							lowerCAmelCase__ ,       lowerCAmelCase__   = self._locate_node(snake_case__  )

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




					def     _SCREAMING_SNAKE_CASE    (						self    :  Union[str, Any]	,    snake_case__    :  KT	,    snake_case__    :  VT  ):
							lowerCAmelCase__ ,       lowerCAmelCase__   = self._locate_node(snake_case__  )
							if node is not None:
									lowerCAmelCase__   = value
							else:
									lowerCAmelCase__   = self.random_level()

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

									lowerCAmelCase__   = Node(snake_case__	,    snake_case__  )

									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(snake_case__  )
											else:
													lowerCAmelCase__   = new_node




					def     _SCREAMING_SNAKE_CASE    (						self    :  Union[str, Any]	,    snake_case__    :  VT  ):
							lowerCAmelCase__ ,       lowerCAmelCase__   = self._locate_node(snake_case__  )

							if node is not None:
									return node.value

							return None







def 				_UpperCAmelCase		(							):





		"""simple docstring"""




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

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

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




		lowerCAmelCase__   = 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  )

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

		if len(lowerCamelCase__  ) != 4:
				print()
		assert len(lowerCamelCase__  ) == 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"""




		lowerCAmelCase__   = SkipList()
		assert skip_list.find("""Some key"""  ) is None







def 				_UpperCAmelCase		(							):





		"""simple docstring"""




		lowerCAmelCase__   = 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"""




		lowerCAmelCase__   = SkipList()
		skip_list.delete("""Some key"""  )

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







def 				_UpperCAmelCase		(							):





		"""simple docstring"""




		lowerCAmelCase__   = 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"""




		lowerCAmelCase__   = 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"""




		lowerCAmelCase__   = SkipList()

		skip_list.insert("""Key1"""      ,	12  )
		skip_list.insert("""V"""      ,	13  )
		skip_list.insert("""X"""      ,	142  )
		skip_list.insert("""Key2"""      ,	15  )

		skip_list.delete("""X"""  )

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

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







def 				_UpperCAmelCase		(							):





		"""simple docstring"""




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

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







def 				_UpperCAmelCase		(							):





		"""simple docstring"""




		for _ in range(100  ):
				# 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"""




		lowerCAmelCase__   = 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(lowerCamelCase__  )


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			main()





"""simple docstring"""




import logging
import os
import threading
import time


try:
			import warnings
except ImportError:
			__lowerCAmelCase     :				Optional[int]    				=    None

try:
			import msvcrt
except ImportError:
			__lowerCAmelCase     :				List[Any]    				=    None

try:
			import fcntl
except ImportError:
			__lowerCAmelCase     :				Optional[int]    				=    None


# Backward compatibility
# ------------------------------------------------
try:
			TimeoutError
except NameError:
			__lowerCAmelCase     :				int    				=    OSError


# Data
# ------------------------------------------------
__lowerCAmelCase     :				Dict    				=    [
    "Timeout",
    "BaseFileLock",
    "WindowsFileLock",
    "UnixFileLock",
    "SoftFileLock",
    "FileLock",
]

__lowerCAmelCase     :				str    				=    "3.0.12"


__lowerCAmelCase     :				Optional[int]    				=    None







def 				_UpperCAmelCase		(							):





		"""simple docstring"""




		global _logger
		lowerCAmelCase__   = _logger or logging.getLogger(__name__  )
		return _logger

class    a_   (  __UpperCamelCase      ):




					def __init__(						self    :  str	,    snake_case__    :  Optional[int]  ):
							lowerCAmelCase__   = lock_file
							return None




					def __str__(						self    :  Any  ):
							lowerCAmelCase__   = F"""The file lock '{self.lock_file}' could not be acquired."""
							return temp

class    a_   :




					def __init__(						self    :  Tuple	,    snake_case__    :  Optional[int]  ):
							lowerCAmelCase__   = lock
							return None




					def __enter__(						self    :  Union[str, Any]  ):
							return self.lock




					def __exit__(						self    :  List[Any]	,    snake_case__    :  Dict	,    snake_case__    :  str	,    snake_case__    :  List[Any]  ):
							self.lock.release()
							return None

class    a_   :




					def __init__(						self    :  Dict	,    snake_case__    :  Tuple	,    snake_case__    :  Dict=-1	,    snake_case__    :  Dict=None  ):
							lowerCAmelCase__   = max_filename_length if max_filename_length is not None else 255
							# Hash the filename if it's too long
							lowerCAmelCase__   = self.hash_filename_if_too_long(snake_case__	,    snake_case__  )
							# The path to the lock file.
							lowerCAmelCase__   = lock_file

							# The file descriptor for the *_lock_file* as it is returned by the
							# os.open() function.
							# This file lock is only NOT None, if the object currently holds the
							# lock.
							lowerCAmelCase__   = None

							# The default timeout value.
							lowerCAmelCase__   = timeout

							# We use this lock primarily for the lock counter.
							lowerCAmelCase__   = threading.Lock()

							# The lock counter is used for implementing the nested locking
							# mechanism. Whenever the lock is acquired, the counter is increased and
							# the lock is only released, when this value is 0 again.
							lowerCAmelCase__   = 0
							return None




					@property
					def     _SCREAMING_SNAKE_CASE    (						self    :  Tuple  ):
							return self._lock_file




					@property
					def     _SCREAMING_SNAKE_CASE    (						self    :  Union[str, Any]  ):
							return self._timeout




					@timeout.setter
					def     _SCREAMING_SNAKE_CASE    (						self    :  str	,    snake_case__    :  str  ):
							lowerCAmelCase__   = float(snake_case__  )
							return None




					def     _SCREAMING_SNAKE_CASE    (						self    :  List[str]  ):
							raise NotImplementedError()




					def     _SCREAMING_SNAKE_CASE    (						self    :  str  ):
							raise NotImplementedError()




					@property
					def     _SCREAMING_SNAKE_CASE    (						self    :  str  ):
							return self._lock_file_fd is not None




					def     _SCREAMING_SNAKE_CASE    (						self    :  List[Any]	,    snake_case__    :  Union[str, Any]=None	,    snake_case__    :  Optional[int]=0.05  ):
							# Use the default timeout, if no timeout is provided.
							if timeout is None:
									lowerCAmelCase__   = self.timeout

							# Increment the number right at the beginning.
							# We can still undo it, if something fails.
							with self._thread_lock:
									self._lock_counter += 1

							lowerCAmelCase__   = id(self  )
							lowerCAmelCase__   = self._lock_file
							lowerCAmelCase__   = time.time()
							try:
									while True:
											with self._thread_lock:
													if not self.is_locked:
															logger().debug(F"""Attempting to acquire lock {lock_id} on {lock_filename}"""  )
															self._acquire()

											if self.is_locked:
													logger().debug(F"""Lock {lock_id} acquired on {lock_filename}"""  )
													break
											elif timeout >= 0 and time.time() - start_time > timeout:
													logger().debug(F"""Timeout on acquiring lock {lock_id} on {lock_filename}"""  )
													raise Timeout(self._lock_file  )
											else:
													logger().debug(
													    F"""Lock {lock_id} not acquired on {lock_filename}, waiting {poll_intervall} seconds ..."""  )
													time.sleep(snake_case__  )
							except:  # noqa
									# Something did go wrong, so decrement the counter.
									with self._thread_lock:
											lowerCAmelCase__   = max(0	,    self._lock_counter - 1  )

									raise
							return _Acquire_ReturnProxy(lock=self  )




					def     _SCREAMING_SNAKE_CASE    (						self    :  Optional[int]	,    snake_case__    :  Tuple=False  ):
							with self._thread_lock:
									if self.is_locked:
											self._lock_counter -= 1

											if self._lock_counter == 0 or force:
													lowerCAmelCase__   = id(self  )
													lowerCAmelCase__   = self._lock_file

													logger().debug(F"""Attempting to release lock {lock_id} on {lock_filename}"""  )
													self._release()
													lowerCAmelCase__   = 0
													logger().debug(F"""Lock {lock_id} released on {lock_filename}"""  )

							return None




					def __enter__(						self    :  Optional[Any]  ):
							self.acquire()
							return self




					def __exit__(						self    :  Any	,    snake_case__    :  Optional[Any]	,    snake_case__    :  Optional[Any]	,    snake_case__    :  Optional[Any]  ):
							self.release()
							return None




					def __del__(						self    :  Optional[int]  ):
							self.release(force=snake_case__  )
							return None




					def     _SCREAMING_SNAKE_CASE    (						self    :  Optional[int]	,    snake_case__    :  str	,    snake_case__    :  int  ):
							lowerCAmelCase__   = os.path.basename(snake_case__  )
							if len(snake_case__  ) > max_length and max_length > 0:
									lowerCAmelCase__   = os.path.dirname(snake_case__  )
									lowerCAmelCase__   = str(hash(snake_case__  )  )
									lowerCAmelCase__   = filename[: max_length - len(snake_case__  ) - 8] + """...""" + hashed_filename + """.lock"""
									return os.path.join(snake_case__	,    snake_case__  )
							else:
									return path

class    a_   (  __UpperCamelCase      ):




					def __init__(						self    :  List[Any]	,    snake_case__    :  int	,    snake_case__    :  str=-1	,    snake_case__    :  Tuple=None  ):
							from .file_utils import relative_to_absolute_path

							super().__init__(snake_case__	,    timeout=snake_case__	,    max_filename_length=snake_case__  )
							lowerCAmelCase__   = """\\\\?\\""" + relative_to_absolute_path(self.lock_file  )




					def     _SCREAMING_SNAKE_CASE    (						self    :  Tuple  ):
							lowerCAmelCase__   = os.O_RDWR | os.O_CREAT | os.O_TRUNC

							try:
									lowerCAmelCase__   = os.open(self._lock_file	,    snake_case__  )
							except OSError:
									pass
							else:
									try:
											msvcrt.locking(snake_case__	,    msvcrt.LK_NBLCK	,    1  )
									except OSError:
											os.close(snake_case__  )
									else:
											lowerCAmelCase__   = fd
							return None




					def     _SCREAMING_SNAKE_CASE    (						self    :  Optional[int]  ):
							lowerCAmelCase__   = self._lock_file_fd
							lowerCAmelCase__   = None
							msvcrt.locking(snake_case__	,    msvcrt.LK_UNLCK	,    1  )
							os.close(snake_case__  )

							try:
									os.remove(self._lock_file  )
							# Probably another instance of the application
							# that acquired the file lock.
							except OSError:
									pass
							return None

class    a_   (  __UpperCamelCase      ):




					def __init__(						self    :  Union[str, Any]	,    snake_case__    :  List[str]	,    snake_case__    :  str=-1	,    snake_case__    :  List[str]=None  ):
							lowerCAmelCase__   = os.statvfs(os.path.dirname(snake_case__  )  ).f_namemax
							super().__init__(snake_case__	,    timeout=snake_case__	,    max_filename_length=snake_case__  )




					def     _SCREAMING_SNAKE_CASE    (						self    :  Optional[Any]  ):
							lowerCAmelCase__   = os.O_RDWR | os.O_CREAT | os.O_TRUNC
							lowerCAmelCase__   = os.open(self._lock_file	,    snake_case__  )

							try:
									fcntl.flock(snake_case__	,    fcntl.LOCK_EX | fcntl.LOCK_NB  )
							except OSError:
									os.close(snake_case__  )
							else:
									lowerCAmelCase__   = fd
							return None




					def     _SCREAMING_SNAKE_CASE    (						self    :  str  ):
							# Do not remove the lockfile:
							#
							#   https://github.com/benediktschmitt/py-filelock/issues/31
							#   https://stackoverflow.com/questions/17708885/flock-removing-locked-file-without-race-condition
							lowerCAmelCase__   = self._lock_file_fd
							lowerCAmelCase__   = None
							fcntl.flock(snake_case__	,    fcntl.LOCK_UN  )
							os.close(snake_case__  )
							return None

class    a_   (  __UpperCamelCase      ):




					def     _SCREAMING_SNAKE_CASE    (						self    :  Tuple  ):
							lowerCAmelCase__   = os.O_WRONLY | os.O_CREAT | os.O_EXCL | os.O_TRUNC
							try:
									lowerCAmelCase__   = os.open(self._lock_file	,    snake_case__  )
							except OSError:
									pass
							else:
									lowerCAmelCase__   = fd
							return None




					def     _SCREAMING_SNAKE_CASE    (						self    :  Optional[int]  ):
							os.close(self._lock_file_fd  )
							lowerCAmelCase__   = None

							try:
									os.remove(self._lock_file  )
							# The file is already deleted and that's what we want.
							except OSError:
									pass
							return None
__lowerCAmelCase     :				Optional[int]    				=    None

if msvcrt:
			__lowerCAmelCase     :				Tuple    				=    WindowsFileLock
elif fcntl:
			__lowerCAmelCase     :				Optional[int]    				=    UnixFileLock
else:
			__lowerCAmelCase     :				Tuple    				=    SoftFileLock

			if warnings is not None:
						warnings.warn("only soft file lock is available")




