




'''simple docstring'''





from typing import Any


class 							__UpperCamelCase			:





				'''simple docstring'''



				def __init__( self       , UpperCAmelCase_						):
											lowerCAmelCase   =		data
											lowerCAmelCase   =		None






				def __repr__( self						):
											return F"""Node({self.data})"""




class 							__UpperCamelCase			:





				'''simple docstring'''



				def __init__( self						):
											lowerCAmelCase   =		None



				def __iter__( self						):
											lowerCAmelCase   =		self.head
											while node:
																		yield node.data
																		lowerCAmelCase   =		node.next



				def __len__( self						):
											return sum(1 for _ in self						)



				def __repr__( self						):
											return "->".join([str(__A						) for item in self]						)



				def __getitem__( self       , UpperCAmelCase_						):
											if not 0 <= index < len(self						):
																		raise ValueError('''list index out of range.'''						)
											for i, node in enumerate(self						):
																		if i == index:
																									return node
											return None



				def __setitem__( self       , UpperCAmelCase_       , UpperCAmelCase_						):
											if not 0 <= index < len(self						):
																		raise ValueError('''list index out of range.'''						)
											lowerCAmelCase   =		self.head
											for _ in range(__A						):
																		lowerCAmelCase   =		current.next
											lowerCAmelCase   =		data



				def       __snake_case		( self       , UpperCAmelCase_						):
											self.insert_nth(len(self						)       , __A						)



				def       __snake_case		( self       , UpperCAmelCase_						):
											self.insert_nth(0       , __A						)



				def       __snake_case		( self       , UpperCAmelCase_       , UpperCAmelCase_						):
											if not 0 <= index <= len(self						):
																		raise IndexError('''list index out of range'''						)
											lowerCAmelCase   =		Node(__A						)
											if self.head is None:
																		lowerCAmelCase   =		new_node
											elif index == 0:
																		lowerCAmelCase   =		self.head  # link new_node to head
																		lowerCAmelCase   =		new_node
											else:
																		lowerCAmelCase   =		self.head
																		for _ in range(index - 1						):
																									lowerCAmelCase   =		temp.next
																		lowerCAmelCase   =		temp.next
																		lowerCAmelCase   =		new_node



				def       __snake_case		( self						):  # print every node data
											print(self						)



				def       __snake_case		( self						):
											return self.delete_nth(0						)



				def       __snake_case		( self						):  # delete from tail
											return self.delete_nth(len(self						) - 1						)



				def       __snake_case		( self       , UpperCAmelCase_ = 0						):
											if not 0 <= index <= len(self						) - 1:  # test if index is valid
																		raise IndexError('''List index out of range.'''						)
											lowerCAmelCase   =		self.head  # default first node
											if index == 0:
																		lowerCAmelCase   =		self.head.next
											else:
																		lowerCAmelCase   =		self.head
																		for _ in range(index - 1						):
																									lowerCAmelCase   =		temp.next
																		lowerCAmelCase   =		temp.next
																		lowerCAmelCase   =		temp.next.next
											return delete_node.data



				def       __snake_case		( self						):
											return self.head is None






				def       __snake_case		( self						):
											lowerCAmelCase   =		None
											lowerCAmelCase   =		self.head

											while current:
																		# Store the current node's next node.
																		lowerCAmelCase   =		current.next
																		# Make the current node's next point backwards
																		lowerCAmelCase   =		prev
																		# Make the previous node be the current node
																		lowerCAmelCase   =		current
																		# Make the current node the next node (to progress iteration)
																		lowerCAmelCase   =		next_node
											# Return prev in order to put the head at the end
											lowerCAmelCase   =		prev




def       UpperCAmelCase       (     ):
							lowerCAmelCase   =		LinkedList()
							assert linked_list.is_empty() is True
							assert str(_lowerCAmelCase							) == ""

							try:
														linked_list.delete_head()
														raise AssertionError  # This should not happen.
							except IndexError:
														assert True  # This should happen.

							try:
														linked_list.delete_tail()
														raise AssertionError  # This should not happen.
							except IndexError:
														assert True  # This should happen.

							for i in range(10							):
														assert len(_lowerCAmelCase							) == i
														linked_list.insert_nth(_lowerCAmelCase						, i + 1							)
							assert str(_lowerCAmelCase							) == "->".join(str(_lowerCAmelCase							) for i in range(1						, 11							)							)

							linked_list.insert_head(0							)
							linked_list.insert_tail(11							)
							assert str(_lowerCAmelCase							) == "->".join(str(_lowerCAmelCase							) for i in range(0						, 12							)							)

							assert linked_list.delete_head() == 0
							assert linked_list.delete_nth(9							) == 10
							assert linked_list.delete_tail() == 11
							assert len(_lowerCAmelCase							) == 9
							assert str(_lowerCAmelCase							) == "->".join(str(_lowerCAmelCase							) for i in range(1						, 10							)							)

							assert all(linked_list[i] == i + 1 for i in range(0						, 9							)							) is True

							for i in range(0						, 9							):
														lowerCAmelCase   =		-i
							assert all(linked_list[i] == -i for i in range(0						, 9							)							) is True

							linked_list.reverse()
							assert str(_lowerCAmelCase							) == "->".join(str(_lowerCAmelCase							) for i in range(-8						, 1							)							)



def       UpperCAmelCase       (     ):
							lowerCAmelCase   =		[
							    -9,
							    100,
							    Node(77345112							),
							    "dlrow olleH",
							    7,
							    5555,
							    0,
							    -192.55555,
							    "Hello, world!",
							    77.9,
							    Node(10							),
							    None,
							    None,
							    12.20,
							]
							lowerCAmelCase   =		LinkedList()

							for i in test_input:
														linked_list.insert_tail(_lowerCAmelCase							)

							# Check if it's empty or not
							assert linked_list.is_empty() is False
							assert (
							    str(_lowerCAmelCase							) == "-9->100->Node(77345112)->dlrow olleH->7->5555->0->"
							    "-192.55555->Hello, world!->77.9->Node(10)->None->None->12.2"
							)

							# Delete the head
							lowerCAmelCase   =		linked_list.delete_head()
							assert result == -9
							assert (
							    str(_lowerCAmelCase							) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
							    "Hello, world!->77.9->Node(10)->None->None->12.2"
							)

							# Delete the tail
							lowerCAmelCase   =		linked_list.delete_tail()
							assert result == 12.2
							assert (
							    str(_lowerCAmelCase							) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
							    "Hello, world!->77.9->Node(10)->None->None"
							)

							# Delete a node in specific location in linked list
							lowerCAmelCase   =		linked_list.delete_nth(10							)
							assert result is None
							assert (
							    str(_lowerCAmelCase							) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
							    "Hello, world!->77.9->Node(10)->None"
							)

							# Add a Node instance to its head
							linked_list.insert_head(Node('''Hello again, world!'''							)							)
							assert (
							    str(_lowerCAmelCase							)
							    == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
							    "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None"
							)

							# Add None to its tail
							linked_list.insert_tail(_lowerCAmelCase							)
							assert (
							    str(_lowerCAmelCase							)
							    == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
							    "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None->None"
							)

							# Reverse the linked list
							linked_list.reverse()
							assert (
							    str(_lowerCAmelCase							)
							    == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
							    "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
							)



def       UpperCAmelCase       (     ):
							from doctest import testmod

							testmod()

							lowerCAmelCase   =		LinkedList()
							linked_list.insert_head(input('''Inserting 1st at head '''							).strip()							)
							linked_list.insert_head(input('''Inserting 2nd at head '''							).strip()							)
							print('''\nPrint list:'''							)
							linked_list.print_list()
							linked_list.insert_tail(input('''\nInserting 1st at tail '''							).strip()							)
							linked_list.insert_tail(input('''Inserting 2nd at tail '''							).strip()							)
							print('''\nPrint list:'''							)
							linked_list.print_list()
							print('''\nDelete head'''							)
							linked_list.delete_head()
							print('''Delete tail'''							)
							linked_list.delete_tail()
							print('''\nPrint list:'''							)
							linked_list.print_list()
							print('''\nReverse linked list'''							)
							linked_list.reverse()
							print('''\nPrint list:'''							)
							linked_list.print_list()
							print('''\nString representation of linked list:'''							)
							print(_lowerCAmelCase							)
							print('''\nReading/changing Node data using indexing:'''							)
							print(F"""Element at Position 1: {linked_list[1]}"""							)
							lowerCAmelCase   =		input('''Enter New Value: '''							).strip()
							print('''New list:'''							)
							print(_lowerCAmelCase							)
							print(F"""length of linked_list is : {len(_lowerCAmelCase							)}"""							)


if __name__ == "__main__":
		main()









import io
import itertools
import json
from dataclasses import dataclass
from typing import Optional

import pyarrow as pa
import pyarrow.json as paj

import datasets
from datasets.table import table_cast
from datasets.utils.file_utils import readline


UpperCAmelCase_						=datasets.utils.logging.get_logger(__name__)


@dataclass
class 							__UpperCamelCase			( datasets.BuilderConfig  ):





				'''simple docstring'''



				__a							: Optional[datasets.Features]										=None
				__a							: str										="utf-8"
				__a							: Optional[str]										=None
				__a							: Optional[str]										=None
				__a							: bool										=True  # deprecated
				__a							: Optional[int]										=None  # deprecated
				__a							: int										=1_0 << 2_0  # 10MB
				__a							: Optional[bool]										=None




class 							__UpperCamelCase			( datasets.ArrowBasedBuilder  ):





				'''simple docstring'''



				__a							: str										=JsonConfig



				def       __snake_case		( self						):
											if self.config.block_size is not None:
																		logger.warning('''The JSON loader parameter `block_size` is deprecated. Please use `chunksize` instead'''						)
																		lowerCAmelCase   =		self.config.block_size
											if self.config.use_threads is not True:
																		logger.warning(
																		    '''The JSON loader parameter `use_threads` is deprecated and doesn\'t have any effect anymore.'''						)
											if self.config.newlines_in_values is not None:
																		raise ValueError('''The JSON loader parameter `newlines_in_values` is no longer supported'''						)
											return datasets.DatasetInfo(features=self.config.features						)



				def       __snake_case		( self       , UpperCAmelCase_						):
											if not self.config.data_files:
																		raise ValueError(F"""At least one data file must be specified, but got data_files={self.config.data_files}"""						)
											lowerCAmelCase   =		dl_manager.download_and_extract(self.config.data_files						)
											if isinstance(UpperCAmelCase_       , (str, list, tuple)						):
																		lowerCAmelCase   =		data_files
																		if isinstance(UpperCAmelCase_       , UpperCAmelCase_						):
																									lowerCAmelCase   =		[files]
																		lowerCAmelCase   =		[dl_manager.iter_files(UpperCAmelCase_						) for file in files]
																		return [datasets.SplitGenerator(name=datasets.Split.TRAIN       , gen_kwargs={'''files''': files}						)]
											lowerCAmelCase   =		[]
											for split_name, files in data_files.items():
																		if isinstance(UpperCAmelCase_       , UpperCAmelCase_						):
																									lowerCAmelCase   =		[files]
																		lowerCAmelCase   =		[dl_manager.iter_files(UpperCAmelCase_						) for file in files]
																		splits.append(datasets.SplitGenerator(name=UpperCAmelCase_       , gen_kwargs={'''files''': files}						)						)
											return splits



				def       __snake_case		( self       , UpperCAmelCase_						):
											if self.config.features is not None:
																		# adding missing columns
																		for column_name in set(self.config.features						) - set(pa_table.column_names						):
																									lowerCAmelCase   =		self.config.features.arrow_schema.field(UpperCAmelCase_						).type
																									lowerCAmelCase   =		pa_table.append_column(UpperCAmelCase_       , pa.array([None] * len(UpperCAmelCase_						)       , type=UpperCAmelCase_						)						)
																		# more expensive cast to support nested structures with keys in a different order
																		# allows str <-> int/float or str to Audio for example
																		lowerCAmelCase   =		table_cast(UpperCAmelCase_       , self.config.features.arrow_schema						)
											return pa_table






				def       __snake_case		( self       , UpperCAmelCase_						):
											for file_idx, file in enumerate(itertools.chain.from_iterable(UpperCAmelCase_						)						):
																		# If the file is one json object and if we need to look at the list of items in one specific field
																		if self.config.field is not None:
																									with open(UpperCAmelCase_       , encoding=self.config.encoding       , errors=self.config.encoding_errors						) as f:
																																lowerCAmelCase   =		json.load(UpperCAmelCase_						)

																									# We keep only the field we are interested in
																									lowerCAmelCase   =		dataset[self.config.field]

																									# We accept two format: a list of dicts or a dict of lists
																									if isinstance(UpperCAmelCase_       , (list, tuple)						):
																																lowerCAmelCase   =		set().union(*[row.keys() for row in dataset]						)
																																lowerCAmelCase   =		{col: [row.get(UpperCAmelCase_						) for row in dataset] for col in keys}
																									else:
																																lowerCAmelCase   =		dataset
																									lowerCAmelCase   =		pa.Table.from_pydict(UpperCAmelCase_						)
																									yield file_idx, self._cast_table(UpperCAmelCase_						)

																		# If the file has one json object per line
																		else:
																									with open(UpperCAmelCase_       , '''rb'''						) as f:
																																lowerCAmelCase   =		0
																																# Use block_size equal to the chunk size divided by 32 to leverage multithreading
																																# Set a default minimum value of 16kB if the chunk size is really small
																																lowerCAmelCase   =		max(self.config.chunksize // 32       , 16 << 10						)
																																lowerCAmelCase   =		(
																																    self.config.encoding_errors if self.config.encoding_errors is not None else '''strict'''
																																)
																																while True:
																																							lowerCAmelCase   =		f.read(self.config.chunksize						)
																																							if not batch:
																																														break
																																							# Finish current line
																																							try:
																																														batch += f.readline()
																																							except (AttributeError, io.UnsupportedOperation):
																																														batch += readline(UpperCAmelCase_						)
																																							# PyArrow only accepts utf-8 encoded bytes
																																							if self.config.encoding != "utf-8":
																																														lowerCAmelCase   =		batch.decode(self.config.encoding       , errors=UpperCAmelCase_						).encode('''utf-8'''						)
																																							try:
																																														while True:
																																																					try:
																																																												lowerCAmelCase   =		paj.read_json(
																																																												    io.BytesIO(UpperCAmelCase_						)       , read_options=paj.ReadOptions(block_size=UpperCAmelCase_						)						)
																																																												break
																																																					except (pa.ArrowInvalid, pa.ArrowNotImplementedError) as e:
																																																												if (
																																																												    isinstance(UpperCAmelCase_       , pa.ArrowInvalid						)
																																																												    and "straddling" not in str(UpperCAmelCase_						)
																																																												    or block_size > len(UpperCAmelCase_						)
																																																												):
																																																																			raise
																																																												else:
																																																																			# Increase the block size in case it was too small.
																																																																			# The block size will be reset for the next file.
																																																																			logger.debug(
																																																																			    F"""Batch of {len(UpperCAmelCase_						)} bytes couldn't be parsed with block_size={block_size}. Retrying with block_size={block_size * 2}."""						)
																																																																			block_size *= 2
																																							except pa.ArrowInvalid as e:
																																														try:
																																																					with open(
																																																					    UpperCAmelCase_       , encoding=self.config.encoding       , errors=self.config.encoding_errors						) as f:
																																																												lowerCAmelCase   =		json.load(UpperCAmelCase_						)
																																														except json.JSONDecodeError:
																																																					logger.error(F"""Failed to read file '{file}' with error {type(UpperCAmelCase_						)}: {e}"""						)
																																																					raise e
																																														# If possible, parse the file as a list of json objects and exit the loop
																																														if isinstance(UpperCAmelCase_       , UpperCAmelCase_						):  # list is the only sequence type supported in JSON
																																																					try:
																																																												lowerCAmelCase   =		set().union(*[row.keys() for row in dataset]						)
																																																												lowerCAmelCase   =		{col: [row.get(UpperCAmelCase_						) for row in dataset] for col in keys}
																																																												lowerCAmelCase   =		pa.Table.from_pydict(UpperCAmelCase_						)
																																																					except (pa.ArrowInvalid, AttributeError) as e:
																																																												logger.error(F"""Failed to read file '{file}' with error {type(UpperCAmelCase_						)}: {e}"""						)
																																																												raise ValueError(F"""Not able to read records in the JSON file at {file}."""						) from None
																																																					yield file_idx, self._cast_table(UpperCAmelCase_						)
																																																					break
																																														else:
																																																					logger.error(F"""Failed to read file '{file}' with error {type(UpperCAmelCase_						)}: {e}"""						)
																																																					raise ValueError(
																																																					    F"""Not able to read records in the JSON file at {file}. """
																																																					    F"""You should probably indicate the field of the JSON file containing your records. """
																																																					    F"""This JSON file contain the following fields: {str(list(dataset.keys()						)						)}. """
																																																					    F"""Select the correct one and provide it as `field='XXX'` to the dataset loading method. """						) from None
                        # Uncomment for debugging (will print the Arrow table size and elements)
                        # logger.warning(f"pa_table: {pa_table} num rows: {pa_table.num_rows}")
                        # logger.warning('\n'.join(str(pa_table.slice(i, 1).to_pydict()) for i in range(pa_table.num_rows)))
																																							yield (file_idx, batch_idx), self._cast_table(UpperCAmelCase_						)
																																							batch_idx += 1



