





from __future__ import annotations

from collections import deque
from enum import Enum
from math import atana, degrees
from sys import maxsize

class      A_	(a_      ):
	UpperCAmelCase__ =      1
	UpperCAmelCase__ =      2
	UpperCAmelCase__ =      3
	def __repr__(   self		):






				'''simple docstring'''







				return F"""{self.__class__.__name__}.{self.name}"""





def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__			)  ->    float:







			'''simple docstring'''

			UpperCAmelCase		,      UpperCAmelCase       		=    point
			return degrees(atana(y - miny      ,      x - minx			)			)





def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__			)  ->    Direction:







			'''simple docstring'''

			UpperCAmelCase		,      UpperCAmelCase       		=    starting
			UpperCAmelCase		,      UpperCAmelCase       		=    via
			UpperCAmelCase		,      UpperCAmelCase       		=    target
			UpperCAmelCase       		=    degrees(atana(ya - ya      ,      xa - xa			)			)
			via_angle %= 360
			UpperCAmelCase       		=    degrees(atana(ya - ya      ,      xa - xa			)			)
			target_angle %= 360
			# t-
			#  \ \
			#   \ v
			#    \|
			#     s
			# via_angle is always lower than target_angle, if direction is left.
			# If they are same, it means they are on a same line of convex hull.
			if target_angle > via_angle:
						return Direction.left
			elif target_angle == via_angle:
						return Direction.straight
			else:
						return Direction.right






def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__			)  ->    list[tuple[int, int]]:







			'''simple docstring'''

			if len(UpperCamelCase__			) <= 2:
						# There is no convex hull
						raise ValueError('''graham_scan: argument must contain more than 3 points.'''			)
			if len(UpperCamelCase__			) == 3:
						return points
			# find the lowest and the most left point
			UpperCAmelCase       		=    0
			UpperCAmelCase		,      UpperCAmelCase       		=    maxsize, maxsize
			for i, point in enumerate(UpperCamelCase__			):
						UpperCAmelCase       		=    point[0]
						UpperCAmelCase       		=    point[1]
						if y < miny:
									UpperCAmelCase       		=    y
									UpperCAmelCase       		=    x
									UpperCAmelCase       		=    i
						if y == miny and x < minx:
									UpperCAmelCase       		=    x
									UpperCAmelCase       		=    i

    # remove the lowest and the most left point from points for preparing for sort
			points.pop(UpperCamelCase__			)

			UpperCAmelCase       		=    sorted(UpperCamelCase__      ,      key=lambda UpperCamelCase__			: angle_comparer(UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__			)			)
			# This insert actually costs complexity,
			# and you should instead add (minx, miny) into stack later.
			# I'm using insert just for easy understanding.
			sorted_points.insert(0      ,      (minx, miny)			)

			UpperCAmelCase       		=    deque()
			stack.append(sorted_points[0]			)
			stack.append(sorted_points[1]			)
			stack.append(sorted_points[2]			)
			# In any ways, the first 3 points line are towards left.
			# Because we sort them the angle from minx, miny.
			UpperCAmelCase       		=    Direction.left

			for i in range(3      ,      len(UpperCamelCase__			)			):
						while True:
									UpperCAmelCase       		=    stack[-2]
									UpperCAmelCase       		=    stack[-1]
									UpperCAmelCase       		=    sorted_points[i]
									UpperCAmelCase       		=    check_direction(UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__			)

									if next_direction == Direction.left:
												UpperCAmelCase       		=    Direction.left
												break
									if next_direction == Direction.straight:
												if current_direction == Direction.left:
															# We keep current_direction as left.
															# Because if the straight line keeps as straight,
															# we want to know if this straight line is towards left.
															break
												elif current_direction == Direction.right:
															# If the straight line is towards right,
															# every previous points on those straigh line is not convex hull.
															stack.pop()
									if next_direction == Direction.right:
												stack.pop()
						stack.append(sorted_points[i]			)
			return list(UpperCamelCase__			)










import textwrap

import pyarrow as pa
import pytest

from datasets import Features, Value
from datasets.packaged_modules.json.json import Json





@pytest.fixture
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__			)  ->    str:







			'''simple docstring'''

			UpperCAmelCase       		=    tmp_path / '''file.jsonl'''
			UpperCAmelCase       		=    textwrap.dedent(
			    '''\
        {"col_1": -1}
        {"col_1": 1, "col_2": 2}
        {"col_1": 10, "col_2": 20}
        '''			)
			with open(UpperCamelCase__      ,      '''w'''			) as f:
						f.write(UpperCamelCase__			)
			return str(UpperCamelCase__			)





@pytest.fixture
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__			)  ->    Union[str, Any]:







			'''simple docstring'''

			UpperCAmelCase       		=    tmp_path / '''file_utf16_encoded.jsonl'''
			UpperCAmelCase       		=    textwrap.dedent(
			    '''\
        {"col_1": -1}
        {"col_1": 1, "col_2": 2}
        {"col_1": 10, "col_2": 20}
        '''			)
			with open(UpperCamelCase__      ,      '''w'''      ,      encoding='''utf-16'''			) as f:
						f.write(UpperCamelCase__			)
			return str(UpperCamelCase__			)





@pytest.fixture
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__			)  ->    Optional[Any]:







			'''simple docstring'''

			UpperCAmelCase       		=    tmp_path / '''file_with_list_of_dicts.json'''
			UpperCAmelCase       		=    textwrap.dedent(
			    '''\
        [
            {"col_1": -1},
            {"col_1": 1, "col_2": 2},
            {"col_1": 10, "col_2": 20}
        ]
        '''			)
			with open(UpperCamelCase__      ,      '''w'''			) as f:
						f.write(UpperCamelCase__			)
			return str(UpperCamelCase__			)





@pytest.fixture
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__			)  ->    int:







			'''simple docstring'''

			UpperCAmelCase       		=    tmp_path / '''file_with_list_of_dicts_field.json'''
			UpperCAmelCase       		=    textwrap.dedent(
			    '''\
        {
            "field1": 1,
            "field2": "aabb",
            "field3": [
                {"col_1": -1},
                {"col_1": 1, "col_2": 2},
                {"col_1": 10, "col_2": 20}
            ]
        }
        '''			)
			with open(UpperCamelCase__      ,      '''w'''			) as f:
						f.write(UpperCamelCase__			)
			return str(UpperCamelCase__			)





@pytest.mark.parametrize(
    '''file_fixture, config_kwargs'''      ,      [
        ('''jsonl_file''', {}),
        ('''jsonl_file_utf16_encoded''', {'''encoding''': '''utf-16'''}),
        ('''json_file_with_list_of_dicts''', {}),
        ('''json_file_with_list_of_dicts_field''', {'''field''': '''field3'''}),
    ]      ,      )
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__			)  ->    Dict:







			'''simple docstring'''

			UpperCAmelCase       		=    Json(**UpperCamelCase__			)
			UpperCAmelCase       		=    json._generate_tables([[request.getfixturevalue(UpperCamelCase__			)]]			)
			UpperCAmelCase       		=    pa.concat_tables([table for _, table in generator]			)
			assert pa_table.to_pydict() == {"col_1": [-1, 1, 10], "col_2": [None, 2, 20]}






@pytest.mark.parametrize(
    '''file_fixture, config_kwargs'''      ,      [
        (
            '''jsonl_file''',
            {'''features''': Features({'''col_1''': Value('''int64'''			), '''col_2''': Value('''int64'''			), '''missing_col''': Value('''string'''			)}			)},
        ),
        (
            '''json_file_with_list_of_dicts''',
            {'''features''': Features({'''col_1''': Value('''int64'''			), '''col_2''': Value('''int64'''			), '''missing_col''': Value('''string'''			)}			)},
        ),
        (
            '''json_file_with_list_of_dicts_field''',
            {
                '''field''': '''field3''',
                '''features''': Features(
                    {'''col_1''': Value('''int64'''			), '''col_2''': Value('''int64'''			), '''missing_col''': Value('''string'''			)}			),
            },
        ),
    ]      ,      )
def 						__SCREAMING_SNAKE_CASE  (    UpperCamelCase__      ,      UpperCamelCase__      ,      UpperCamelCase__			)  ->    List[Any]:







			'''simple docstring'''

			UpperCAmelCase       		=    Json(**UpperCamelCase__			)
			UpperCAmelCase       		=    json._generate_tables([[request.getfixturevalue(UpperCamelCase__			)]]			)
			UpperCAmelCase       		=    pa.concat_tables([table for _, table in generator]			)
			assert pa_table.to_pydict() == {"col_1": [-1, 1, 10], "col_2": [None, 2, 20], "missing_col": [None, None, None]}



