



"""simple docstring"""





class    lowercase__     :







       '''simple docstring'''


       def __init__(							self    :						Optional[int]	,       _UpperCAmelCase    :						int	,       _UpperCAmelCase    :						int=None	,       _UpperCAmelCase    :						int=None					)				->		Dict:


             '''simple docstring'''




             UpperCAmelCase_    				=							data
             UpperCAmelCase_    				=							previous
             UpperCAmelCase_    				=							next_node



       def __str__(							self    :						str					)				->		str:


             '''simple docstring'''




             return F"""{self.data}"""



       def   lowercase__       (							self    :						List[Any]					)				->		int:


             '''simple docstring'''




             return self.data



       def   lowercase__       (							self    :						Dict					)				->		str:


             '''simple docstring'''




             return self.next







       def   lowercase__       (							self    :						Dict					)				->		Dict:


             '''simple docstring'''




             return self.previous



class    lowercase__     :







       '''simple docstring'''


       def __init__(							self    :						List[str]	,       _UpperCAmelCase    :						Union[str, Any]					)				->		str:


             '''simple docstring'''




             UpperCAmelCase_    				=							head



       def __iter__(							self    :						List[Any]					)				->		Dict:


             '''simple docstring'''




             return self







       def   lowercase__       (							self    :						Union[str, Any]					)				->		str:


             '''simple docstring'''




             if not self.current:
                   raise StopIteration
             else:
                   UpperCAmelCase_    				=							self.current.get_data()
                   UpperCAmelCase_    				=							self.current.get_next()
                   return value



class    lowercase__     :







       '''simple docstring'''


       def __init__(							self    :						Union[str, Any]					)				->		Optional[Any]:


             '''simple docstring'''




             UpperCAmelCase_    				=							None  # First node in list
             UpperCAmelCase_    				=							None  # Last node in list



       def __str__(							self    :						Dict					)				->		int:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.head
             UpperCAmelCase_    				=							[]
             while current is not None:
                   nodes.append(current.get_data()					)
                   UpperCAmelCase_    				=							current.get_next()
             return " ".join(str(_UpperCAmelCase					) for node in nodes					)



       def __contains__(							self    :						str	,       _UpperCAmelCase    :						int					)				->		Dict:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.head
             while current:
                   if current.get_data() == value:
                         return True
                   UpperCAmelCase_    				=							current.get_next()
             return False



       def __iter__(							self    :						Union[str, Any]					)				->		Optional[int]:


             '''simple docstring'''




             return LinkedListIterator(self.head					)



       def   lowercase__       (							self    :						str					)				->		str:


             '''simple docstring'''




             if self.head:
                   return self.head.get_data()
             return None



       def   lowercase__       (							self    :						Optional[Any]					)				->		Union[str, Any]:


             '''simple docstring'''




             if self.tail:
                   return self.tail.get_data()
             return None



       def   lowercase__       (							self    :						Union[str, Any]	,       _UpperCAmelCase    :						Node					)				->		None:


             '''simple docstring'''




             if self.head is None:
                   UpperCAmelCase_    				=							node
                   UpperCAmelCase_    				=							node
             else:
                   self.insert_before_node(self.head	,       _UpperCAmelCase					)



       def   lowercase__       (							self    :						List[Any]	,       _UpperCAmelCase    :						Node					)				->		None:


             '''simple docstring'''




             if self.head is None:
                   self.set_head(_UpperCAmelCase					)
             else:
                   self.insert_after_node(self.tail	,       _UpperCAmelCase					)



       def   lowercase__       (							self    :						str	,       _UpperCAmelCase    :						int					)				->		None:


             '''simple docstring'''




             UpperCAmelCase_    				=							Node(_UpperCAmelCase					)
             if self.head is None:
                   self.set_head(_UpperCAmelCase					)
             else:
                   self.set_tail(_UpperCAmelCase					)



       def   lowercase__       (							self    :						List[Any]	,       _UpperCAmelCase    :						Node	,       _UpperCAmelCase    :						Node					)				->		None:


             '''simple docstring'''




             UpperCAmelCase_    				=							node
             UpperCAmelCase_    				=							node.previous

             if node.get_previous() is None:
                   UpperCAmelCase_    				=							node_to_insert
             else:
                   UpperCAmelCase_    				=							node_to_insert

             UpperCAmelCase_    				=							node_to_insert



       def   lowercase__       (							self    :						Tuple	,       _UpperCAmelCase    :						Node	,       _UpperCAmelCase    :						Node					)				->		None:


             '''simple docstring'''




             UpperCAmelCase_    				=							node
             UpperCAmelCase_    				=							node.next

             if node.get_next() is None:
                   UpperCAmelCase_    				=							node_to_insert
             else:
                   UpperCAmelCase_    				=							node_to_insert

             UpperCAmelCase_    				=							node_to_insert



       def   lowercase__       (							self    :						Dict	,       _UpperCAmelCase    :						int	,       _UpperCAmelCase    :						int					)				->		None:


             '''simple docstring'''




             UpperCAmelCase_    				=							1
             UpperCAmelCase_    				=							Node(_UpperCAmelCase					)
             UpperCAmelCase_    				=							self.head
             while node:
                   if current_position == position:
                         self.insert_before_node(_UpperCAmelCase	,       _UpperCAmelCase					)
                         return
                   current_position += 1
                   UpperCAmelCase_    				=							node.next
             self.insert_after_node(self.tail	,       _UpperCAmelCase					)



       def   lowercase__       (							self    :						Tuple	,       _UpperCAmelCase    :						int					)				->		Node:


             '''simple docstring'''




             UpperCAmelCase_    				=							self.head
             while node:
                   if node.get_data() == item:
                         return node
                   UpperCAmelCase_    				=							node.get_next()
             raise Exception("Node not found"					)



       def   lowercase__       (							self    :						Optional[Any]	,       _UpperCAmelCase    :						Optional[int]					)				->		int:


             '''simple docstring'''




             if (node := self.get_node(_UpperCAmelCase					)) is not None:
                   if node == self.head:
                         UpperCAmelCase_    				=							self.head.get_next()

                   if node == self.tail:
                         UpperCAmelCase_    				=							self.tail.get_previous()

                   self.remove_node_pointers(_UpperCAmelCase					)



       @staticmethod
       def   lowercase__       (							_UpperCAmelCase    :						Node					)				->		None:


             '''simple docstring'''




             if node.get_next():
                   UpperCAmelCase_    				=							node.previous

             if node.get_previous():
                   UpperCAmelCase_    				=							node.next

             UpperCAmelCase_    				=							None
             UpperCAmelCase_    				=							None







       def   lowercase__       (							self    :						int					)				->		Tuple:


             '''simple docstring'''




             return self.head is None



def      a__			(   ):
      pass


if __name__ == "__main__":
  import doctest

  doctest.testmod()









"""simple docstring"""





from __future__ import annotations
def      a__			(   lowerCAmelCase__   ):
      if len(lowerCAmelCase__   ) == 0:
            return []
      UpperCAmelCase_				,					UpperCAmelCase_    				=							min(lowerCAmelCase__   ), max(lowerCAmelCase__   )
      UpperCAmelCase_    				=							int(max_value - min_value   ) + 1
      UpperCAmelCase_    				=							[[] for _ in range(lowerCAmelCase__   )]

      for i in my_list:
            buckets[int(i - min_value   )].append(lowerCAmelCase__   )

      return [v for bucket in buckets for v in sorted(lowerCAmelCase__   )]


if __name__ == "__main__":
  from doctest import testmod

  testmod()
  assert bucket_sort([4, 5, 3, 2, 1]) == [1, 2, 3, 4, 5]
  assert bucket_sort([0, 1, -10, 15, 2, -2]) == [-10, -2, 0, 1, 2, 15]




