




from __future__ import annotations


def 		_lowerCamelCase				(					UpperCamelCase					,     UpperCamelCase							)			->		List[str]:





  """simple docstring"""





  _lowercase: Dict						     =    0
  _lowercase: str						     =    len(UpperCamelCase							) - 1
  while left <= right:
    _lowercase: List[str]						     =    (left + right) // 2
    if left == right:
      if sorted_list[middle] < item:
        _lowercase: List[str]						     =    middle + 1
      break
    elif sorted_list[middle] < item:
      _lowercase: Tuple						     =    middle + 1
    else:
      _lowercase: List[str]						     =    middle - 1
  sorted_list.insert(UpperCamelCase					,     UpperCamelCase							)
  return sorted_list


def 		_lowerCamelCase				(					UpperCamelCase					,     UpperCamelCase							)			->		Optional[int]:





  """simple docstring"""





  _lowercase: str						     =    []
  while left and right:
    if left[0][0] < right[0][0]:
      result.append(left.pop(0							)							)
    else:
      result.append(right.pop(0							)							)
  return result + left + right


def 		_lowerCamelCase				(					UpperCamelCase							)			->		Tuple:





  """simple docstring"""





  _lowercase: List[str]						     =    len(UpperCamelCase							)
  if length <= 1:
    return list_ad
  _lowercase: Tuple						     =    length // 2
  return merge(sortlist_ad(list_ad[:middle]							)					,     sortlist_ad(list_ad[middle:]							)							)


def 		_lowerCamelCase				(					UpperCamelCase							)			->		list[int]:





  """simple docstring"""





  if len(UpperCamelCase							) <= 1:
    return collection
  _lowercase: Union[str, Any]						     =    []
  _lowercase: int						     =    False
  for i in range(0					,     len(UpperCamelCase							)					,     2							):
    if i == len(UpperCamelCase							) - 1:
      _lowercase: List[str]						     =    True
    else:
      if collection[i] < collection[i + 1]:
        two_paired_list.append([collection[i], collection[i + 1]]							)
      else:
        two_paired_list.append([collection[i + 1], collection[i]]							)
  _lowercase: str						     =    sortlist_ad(UpperCamelCase							)
  _lowercase: Dict						     =    [i[0] for i in sorted_list_ad]
  result.append(sorted_list_ad[-1][1]							)
  if has_last_odd_item:
    _lowercase: Optional[Any]						     =    collection[-1]
    _lowercase: Optional[int]						     =    binary_search_insertion(UpperCamelCase					,     UpperCamelCase							)
  _lowercase: str						     =    False
  for i in range(len(UpperCamelCase							) - 1							):
    if result[i] == collection[-1] and has_last_odd_item:
      _lowercase: Optional[Any]						     =    True
    _lowercase: Any						     =    sorted_list_ad[i][1]
    # If last_odd_item is inserted before the item's index,
    # you should forward index one more.
    if is_last_odd_item_inserted_before_this_index:
      _lowercase: int						     =    result[: i + 2] + binary_search_insertion(result[i + 2 :]					,     UpperCamelCase							)
    else:
      _lowercase: str						     =    result[: i + 1] + binary_search_insertion(result[i + 1 :]					,     UpperCamelCase							)

  return result


if __name__ == "__main__":
   UpperCAmelCase__						:       List[Any]							=    input('Enter numbers separated by a comma:\n').strip()
   UpperCAmelCase__						:       Tuple							=    [int(item) for item in user_input.split(',')]
   print(merge_insertion_sort(unsorted))






import os
import tempfile
from pathlib import Path
from unittest import TestCase

import pyarrow as pa
import pytest

from datasets.arrow_dataset import Dataset
from datasets.arrow_reader import ArrowReader, BaseReader, FileInstructions, ReadInstruction, make_file_instructions
from datasets.info import DatasetInfo
from datasets.splits import NamedSplit, Split, SplitDict, SplitInfo

from .utils import assert_arrow_memory_doesnt_increase, assert_arrow_memory_increases

class      UpperCAmelCase						(			A   ):






   def  _a						(	self   :       List[str]						,					UpperCamelCase_   :       str						,					UpperCamelCase_   :       Optional[Any]=False     )->			List[str]:
     _lowercase     ,					_lowercase     ,					_lowercase: Dict						     =    (
         filename_skip_take['filename'],
         filename_skip_take['skip'] if 'skip' in filename_skip_take else None,
         filename_skip_take['take'] if 'take' in filename_skip_take else None,
     )
     open(os.path.join(UpperCamelCase_     )						,					'wb'     ).close()
     _lowercase: int						     =    pa.Table.from_pydict({'filename': [Path(UpperCamelCase_     ).name] * 1_00}     )
     if take == -1:
       _lowercase: int						     =    len(UpperCamelCase_     ) - skip
     if skip is not None and take is not None:
       _lowercase: Any						     =    pa_table.slice(UpperCamelCase_						,					UpperCamelCase_     )
     return pa_table

class      UpperCAmelCase						(			A   ):






   def  _a						(	self   :       Any     )->			Dict:
     _lowercase: str						     =    'my_name'
     _lowercase: Optional[int]						     =    SplitInfo(name='train'						,					num_examples=1_00     )
     _lowercase: Dict						     =    SplitInfo(name='test'						,					num_examples=1_00     )
     _lowercase: Any						     =    [train_info, test_info]
     _lowercase: Any						     =    SplitDict()
     split_dict.add(UpperCamelCase_     )
     split_dict.add(UpperCamelCase_     )
     _lowercase: Tuple						     =    DatasetInfo(splits=UpperCamelCase_     )

     with tempfile.TemporaryDirectory() as tmp_dir:
       _lowercase: List[str]						     =    ReaderTest(UpperCamelCase_						,					UpperCamelCase_     )

       _lowercase: Dict						     =    'test[:33%]'
       _lowercase: Optional[Any]						     =    Dataset(**reader.read(UpperCamelCase_						,					UpperCamelCase_						,					UpperCamelCase_     )     )
       self.assertEqual(dset['filename'][0]						,					f'{name}-test'     )
       self.assertEqual(dset.num_rows						,					33     )
       self.assertEqual(dset.num_columns						,					1     )

       _lowercase: Tuple						     =    ['train', 'test[:33%]']
       _lowercase: Union[str, Any]						     =    [Split.TRAIN, ReadInstruction.from_spec('test[:33%]'     )]
       for instructions in [instructionsa, instructionsa]:
         _lowercase: int						     =    [reader.read(UpperCamelCase_						,					UpperCamelCase_						,					UpperCamelCase_     ) for instr in instructions]
         _lowercase     ,					_lowercase: Dict						     =    (Dataset(**UpperCamelCase_     ) for dataset_kwargs in datasets_kwargs)
         self.assertEqual(train_dset['filename'][0]						,					f'{name}-train'     )
         self.assertEqual(train_dset.num_rows						,					1_00     )
         self.assertEqual(train_dset.num_columns						,					1     )
         self.assertIsInstance(train_dset.split						,					UpperCamelCase_     )
         self.assertEqual(str(train_dset.split     )						,					'train'     )
         self.assertEqual(test_dset['filename'][0]						,					f'{name}-test'     )
         self.assertEqual(test_dset.num_rows						,					33     )
         self.assertEqual(test_dset.num_columns						,					1     )
         self.assertIsInstance(test_dset.split						,					UpperCamelCase_     )
         self.assertEqual(str(test_dset.split     )						,					'test[:33%]'     )
         del train_dset, test_dset






   def  _a						(	self   :       Any     )->			List[str]:
     _lowercase: int						     =    'my_name'
     _lowercase: List[str]						     =    SplitInfo(name='train'						,					num_examples=10_00						,					shard_lengths=[1_00] * 10     )
     _lowercase: Optional[Any]						     =    [train_info]
     _lowercase: Optional[int]						     =    SplitDict()
     split_dict.add(UpperCamelCase_     )
     _lowercase: Optional[Any]						     =    DatasetInfo(splits=UpperCamelCase_     )

     with tempfile.TemporaryDirectory() as tmp_dir:
       _lowercase: Optional[int]						     =    ReaderTest(UpperCamelCase_						,					UpperCamelCase_     )

       _lowercase: Any						     =    'train[:33%]'
       _lowercase: List[Any]						     =    Dataset(**reader.read(UpperCamelCase_						,					UpperCamelCase_						,					UpperCamelCase_     )     )
       self.assertEqual(dset['filename'][0]						,					f'{name}-train-00000-of-00010'     )
       self.assertEqual(dset['filename'][-1]						,					f'{name}-train-00003-of-00010'     )
       self.assertEqual(dset.num_rows						,					3_30     )
       self.assertEqual(dset.num_columns						,					1     )






   def  _a						(	self   :       List[Any]     )->			Dict:
     _lowercase: Any						     =    SplitInfo(name='train'						,					num_examples=1_00     )
     _lowercase: List[Any]						     =    SplitInfo(name='test'						,					num_examples=1_00     )
     _lowercase: List[Any]						     =    SplitDict()
     split_dict.add(UpperCamelCase_     )
     split_dict.add(UpperCamelCase_     )
     _lowercase: Union[str, Any]						     =    DatasetInfo(splits=UpperCamelCase_     )

     with tempfile.TemporaryDirectory() as tmp_dir:
       _lowercase: Dict						     =    ReaderTest(UpperCamelCase_						,					UpperCamelCase_     )

       _lowercase: List[Any]						     =    [
           {'filename': os.path.join(UpperCamelCase_						,					'train'     )},
           {'filename': os.path.join(UpperCamelCase_						,					'test'     ), 'skip': 10, 'take': 10},
       ]
       _lowercase: Tuple						     =    Dataset(**reader.read_files(UpperCamelCase_						,					original_instructions='train+test[10:20]'     )     )
       self.assertEqual(dset.num_rows						,					1_10     )
       self.assertEqual(dset.num_columns						,					1     )
       del dset


@pytest.mark.parametrize('in_memory'					,     [False, True]							)
def 		_lowerCamelCase				(					UpperCamelCase					,     UpperCamelCase					,     UpperCamelCase							)			->		Union[str, Any]:





  """simple docstring"""





  _lowercase: Optional[Any]						     =    arrow_file
  with assert_arrow_memory_increases() if in_memory else assert_arrow_memory_doesnt_increase():
    _lowercase: List[Any]						     =    ArrowReader.read_table(UpperCamelCase					,     in_memory=UpperCamelCase							)
  assert table.shape == dataset.data.shape
  assert set(table.column_names							) == set(dataset.data.column_names							)
  assert dict(table.to_pydict()							) == dict(dataset.data.to_pydict()							)  # to_pydict returns OrderedDict


@pytest.mark.parametrize('in_memory'					,     [False, True]							)
def 		_lowerCamelCase				(					UpperCamelCase					,     UpperCamelCase					,     UpperCamelCase							)			->		List[Any]:





  """simple docstring"""





  _lowercase: Any						     =    arrow_file
  _lowercase: Union[str, Any]						     =    ArrowReader(''					,     UpperCamelCase							)
  with assert_arrow_memory_increases() if in_memory else assert_arrow_memory_doesnt_increase():
    _lowercase: Tuple						     =    reader.read_files([{'filename': filename}]					,     in_memory=UpperCamelCase							)
  assert dataset_kwargs.keys() == {"arrow_table", "info", "split"}
  _lowercase: Any						     =    dataset_kwargs['arrow_table']
  assert table.shape == dataset.data.shape
  assert set(table.column_names							) == set(dataset.data.column_names							)
  assert dict(table.to_pydict()							) == dict(dataset.data.to_pydict()							)  # to_pydict returns OrderedDict


def 		_lowerCamelCase				(					)			->		int:





  """simple docstring"""





  assert ReadInstruction('train'					,     to=10					,     unit='abs'							).to_spec() == "train[:10]"
  assert ReadInstruction('train'					,     from_=-80					,     to=10					,     unit='%'							).to_spec() == "train[-80%:10%]"

  _lowercase: List[str]						     =    'train+test'
  assert ReadInstruction.from_spec(UpperCamelCase							).to_spec() == spec_train_test

  _lowercase: Union[str, Any]						     =    'train[2:10]'
  assert ReadInstruction.from_spec(UpperCamelCase							).to_spec() == spec_train_abs

  _lowercase: Any						     =    'train[15%:-20%]'
  assert ReadInstruction.from_spec(UpperCamelCase							).to_spec() == spec_train_pct

  _lowercase: List[Any]						     =    'train[:10%](closest)'
  assert ReadInstruction.from_spec(UpperCamelCase							).to_spec() == "train[:10%]"

  _lowercase: int						     =    'train[:10%](pct1_dropremainder)'
  assert ReadInstruction.from_spec(UpperCamelCase							).to_spec() == spec_train_pct_rounding

  _lowercase: int						     =    'train[:10%](pct1_dropremainder)+test[-10%:](pct1_dropremainder)'
  assert ReadInstruction.from_spec(UpperCamelCase							).to_spec() == spec_train_test_pct_rounding


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





  """simple docstring"""





  _lowercase: int						     =    'dummy'
  _lowercase: Any						     =    [SplitInfo(name='train'					,     num_examples=100							)]
  _lowercase: Any						     =    'train[:33%]'
  _lowercase: Optional[int]						     =    'arrow'
  _lowercase: Optional[int]						     =    'prefix'

  _lowercase: Optional[int]						     =    make_file_instructions(UpperCamelCase					,     UpperCamelCase					,     UpperCamelCase					,     UpperCamelCase					,     UpperCamelCase							)
  assert isinstance(UpperCamelCase					,     UpperCamelCase							)
  assert file_instructions.num_examples == 33
  assert file_instructions.file_instructions == [
      {"filename": os.path.join(UpperCamelCase					,     F'{name}-train.arrow'							), "skip": 0, "take": 33}
  ]

  _lowercase: int						     =    [SplitInfo(name='train'					,     num_examples=100					,     shard_lengths=[10] * 10							)]
  _lowercase: Dict						     =    make_file_instructions(UpperCamelCase					,     UpperCamelCase					,     UpperCamelCase					,     UpperCamelCase					,     UpperCamelCase							)
  assert isinstance(UpperCamelCase					,     UpperCamelCase							)
  assert file_instructions.num_examples == 33
  assert file_instructions.file_instructions == [
      {"filename": os.path.join(UpperCamelCase					,     F'{name}-train-00000-of-00010.arrow'							), "skip": 0, "take": -1},
      {"filename": os.path.join(UpperCamelCase					,     F'{name}-train-00001-of-00010.arrow'							), "skip": 0, "take": -1},
      {"filename": os.path.join(UpperCamelCase					,     F'{name}-train-00002-of-00010.arrow'							), "skip": 0, "take": -1},
      {"filename": os.path.join(UpperCamelCase					,     F'{name}-train-00003-of-00010.arrow'							), "skip": 0, "take": 3},
  ]





@pytest.mark.parametrize('name, expected_exception'					,     [(None, TypeError), ('', ValueError)]							)
def 		_lowerCamelCase				(					UpperCamelCase					,     UpperCamelCase							)			->		Tuple:





  """simple docstring"""





  _lowercase: List[str]						     =    [SplitInfo(name='train'					,     num_examples=100							)]
  _lowercase: List[Any]						     =    'train'
  _lowercase: List[str]						     =    'arrow'
  _lowercase: Optional[Any]						     =    'prefix_path'
  with pytest.raises(UpperCamelCase							):
    _lowercase: List[str]						     =    make_file_instructions(UpperCamelCase					,     UpperCamelCase					,     UpperCamelCase					,     UpperCamelCase					,     UpperCamelCase							)
