data_structures.linked_list.skip_list
=====================================

.. py:module:: data_structures.linked_list.skip_list

.. autoapi-nested-parse::

   Based on "Skip Lists: A Probabilistic Alternative to Balanced Trees" by William Pugh
   https://epaperpress.com/sortsearch/download/skiplist.pdf



Attributes
----------

.. autoapisummary::

   data_structures.linked_list.skip_list.KT
   data_structures.linked_list.skip_list.VT


Classes
-------

.. autoapisummary::

   data_structures.linked_list.skip_list.Node
   data_structures.linked_list.skip_list.SkipList


Functions
---------

.. autoapisummary::

   data_structures.linked_list.skip_list.main
   data_structures.linked_list.skip_list.pytests
   data_structures.linked_list.skip_list.test_delete_doesnt_leave_dead_nodes
   data_structures.linked_list.skip_list.test_delete_removes_only_given_key
   data_structures.linked_list.skip_list.test_deleted_items_are_not_founded_by_find_method
   data_structures.linked_list.skip_list.test_deleting_item_from_empty_list_do_nothing
   data_structures.linked_list.skip_list.test_insert
   data_structures.linked_list.skip_list.test_insert_overrides_existing_value
   data_structures.linked_list.skip_list.test_iter_always_yields_sorted_values
   data_structures.linked_list.skip_list.test_search
   data_structures.linked_list.skip_list.test_searching_empty_list_returns_none


Module Contents
---------------

.. py:class:: Node(key: KT | str = 'root', value: VT | None = None)

   Bases: :py:obj:`Generic`\ [\ :py:obj:`KT`\ , :py:obj:`VT`\ ]


   .. py:method:: __repr__() -> str

      :return: Visual representation of Node

      >>> node = Node("Key", 2)
      >>> repr(node)
      'Node(Key: 2)'



   .. py:attribute:: forward
      :type:  list[Node[KT, VT]]
      :value: []



   .. py:attribute:: key
      :value: 'root'



   .. py:property:: level
      :type: int


      :return: Number of forward references

      >>> node = Node("Key", 2)
      >>> node.level
      0
      >>> node.forward.append(Node("Key2", 4))
      >>> node.level
      1
      >>> node.forward.append(Node("Key3", 6))
      >>> node.level
      2



   .. py:attribute:: value
      :value: None



.. py:class:: SkipList(p: float = 0.5, max_level: int = 16)

   Bases: :py:obj:`Generic`\ [\ :py:obj:`KT`\ , :py:obj:`VT`\ ]


   .. py:method:: __iter__()


   .. py:method:: __str__() -> str

      :return: Visual representation of SkipList

      >>> skip_list = SkipList()
      >>> print(skip_list)
      SkipList(level=0)
      >>> skip_list.insert("Key1", "Value")
      >>> print(skip_list) # doctest: +ELLIPSIS
      SkipList(level=...
      [root]--...
      [Key1]--Key1...
      None    *...
      >>> skip_list.insert("Key2", "OtherValue")
      >>> print(skip_list) # doctest: +ELLIPSIS
      SkipList(level=...
      [root]--...
      [Key1]--Key1...
      [Key2]--Key2...
      None    *...



   .. py:method:: _locate_node(key) -> tuple[Node[KT, VT] | None, list[Node[KT, VT]]]

      :param key: Searched key,
      :return: Tuple with searched node (or None if given key is not present)
               and list of nodes that refer (if key is present) of should refer to
               given node.



   .. py:method:: delete(key: KT)

      :param key: Key to remove from list.

      >>> skip_list = SkipList()
      >>> skip_list.insert(2, "Two")
      >>> skip_list.insert(1, "One")
      >>> skip_list.insert(3, "Three")
      >>> list(skip_list)
      [1, 2, 3]
      >>> skip_list.delete(2)
      >>> list(skip_list)
      [1, 3]



   .. py:method:: find(key: VT) -> VT | None

      :param key: Search key.
      :return: Value associated with given key or None if given key is not present.

      >>> skip_list = SkipList()
      >>> skip_list.find(2)
      >>> skip_list.insert(2, "Two")
      >>> skip_list.find(2)
      'Two'
      >>> skip_list.insert(2, "Three")
      >>> skip_list.find(2)
      'Three'



   .. py:method:: insert(key: KT, value: VT)

      :param key: Key to insert.
      :param value: Value associated with given key.

      >>> skip_list = SkipList()
      >>> skip_list.insert(2, "Two")
      >>> skip_list.find(2)
      'Two'
      >>> list(skip_list)
      [2]



   .. py:method:: random_level() -> int

      :return: Random level from [1, self.max_level] interval.
               Higher values are less likely.



   .. py:attribute:: head
      :type:  Node[KT, VT]


   .. py:attribute:: level
      :value: 0



   .. py:attribute:: max_level
      :value: 16



   .. py:attribute:: p
      :value: 0.5



.. py:function:: main()

   >>> pytests()


.. py:function:: pytests()

.. py:function:: test_delete_doesnt_leave_dead_nodes()

.. py:function:: test_delete_removes_only_given_key()

.. py:function:: test_deleted_items_are_not_founded_by_find_method()

.. py:function:: test_deleting_item_from_empty_list_do_nothing()

.. py:function:: test_insert()

.. py:function:: test_insert_overrides_existing_value()

.. py:function:: test_iter_always_yields_sorted_values()

.. py:function:: test_search()

.. py:function:: test_searching_empty_list_returns_none()

.. py:data:: KT

.. py:data:: VT