
import logging
import pathlib
import re
import sys
from dataclasses import dataclass, field
from typing import Any, Callable, Dict, List, Optional, Set, Union

import datasets
import librosa
import numpy as np
import torch
from lang_trans import arabic
from packaging import version
from torch import nn

from transformers import (
    HfArgumentParser,
    Trainer,
    TrainingArguments,
    WavaVecaCTCTokenizer,
    WavaVecaFeatureExtractor,
    WavaVecaForCTC,
    WavaVecaProcessor,
    is_apex_available,
    trainer_utils,
)


if is_apex_available():
   from apex import amp

if version.parse(version.parse(torch.__version__).base_version) >= version.parse("1.6"):
   __UpperCAmelCase   						=     True
   from torch.cuda.amp import autocast


__UpperCAmelCase   						=     logging.getLogger(__name__)





@dataclass
class 				UpperCamelCase__		:






       """simple docstring"""


       UpperCAmelCase_				       =field(
           metadata={"help": "Path to pretrained model or model identifier from huggingface.co/models"}	)
       UpperCAmelCase_				       =field(
           default=__SCREAMING_SNAKE_CASE       ,    metadata={"help": "Where do you want to store the pretrained models downloaded from huggingface.co"}       ,    )
       UpperCAmelCase_				       =field(
           default=__SCREAMING_SNAKE_CASE       ,    metadata={"help": "Whether to freeze the feature extractor layers of the model."}	)
       UpperCAmelCase_				       =field(
           default=__SCREAMING_SNAKE_CASE       ,    metadata={"help": "Whether to log verbose messages or not."}       ,    )







def  A__ (       __lowerCamelCase,  __lowerCamelCase						):
   logging.basicConfig(
       format='''%(asctime)s - %(levelname)s - %(name)s - %(message)s''',  datefmt='''%m/%d/%Y %H:%M:%S''',  handlers=[logging.StreamHandler(sys.stdout						)],  )
   SCREAMING_SNAKE_CASE_	=      logging.WARNING
   if model_args.verbose_logging:
      SCREAMING_SNAKE_CASE_	=      logging.DEBUG
   elif trainer_utils.is_main_process(training_args.local_rank						):
      SCREAMING_SNAKE_CASE_	=      logging.INFO
   logger.setLevel(__lowerCamelCase						)





@dataclass
class 				UpperCamelCase__		:






       """simple docstring"""


       UpperCAmelCase_				       =field(
           default=__SCREAMING_SNAKE_CASE       ,    metadata={"help": "The name of the dataset to use (via the datasets library)."}	)
       UpperCAmelCase_				       =field(
           default=__SCREAMING_SNAKE_CASE       ,    metadata={"help": "The configuration name of the dataset to use (via the datasets library)."}	)
       UpperCAmelCase_				       =field(
           default="train"       ,    metadata={
               "help": "The name of the training data set split to use (via the datasets library). Defaults to 'train'"
           }       ,    )
       UpperCAmelCase_				       =field(
           default="validation"       ,    metadata={
               "help": (
                   "The name of the validation data set split to use (via the datasets library). Defaults to 'validation'"
               )
           }       ,    )
       UpperCAmelCase_				       =field(
           default="text"       ,    metadata={"help": "Column in the dataset that contains label (target text). Defaults to 'text'"}       ,    )
       UpperCAmelCase_				       =field(
           default="file"       ,    metadata={"help": "Column in the dataset that contains speech file path. Defaults to 'file'"}       ,    )
       UpperCAmelCase_				       =field(
           default=__SCREAMING_SNAKE_CASE       ,    metadata={"help": "Resample loaded audio to target feature extractor's sampling rate or not."}       ,    )
       UpperCAmelCase_				       =field(
           default=__SCREAMING_SNAKE_CASE       ,    metadata={"help": "Filters out examples longer than specified. Defaults to no filtering."}       ,    )
       UpperCAmelCase_				       =field(
           default="librispeech"       ,    metadata={
               "help": (
                   "Orthography used for normalization and tokenization: 'librispeech' (default), 'timit', or"
                   " 'buckwalter'."
               )
           }       ,    )
       UpperCAmelCase_				       =field(
           default=__SCREAMING_SNAKE_CASE       ,    metadata={"help": "Overwrite the cached preprocessed datasets or not."}	)
       UpperCAmelCase_				       =field(
           default=__SCREAMING_SNAKE_CASE       ,    metadata={"help": "The number of processes to use for the preprocessing."}       ,    )







@dataclass
class 				UpperCamelCase__		:






       """simple docstring"""


       UpperCAmelCase_				       =False
       UpperCAmelCase_				       =None
       UpperCAmelCase_				       ="|"
       UpperCAmelCase_				       =field(default_factory=__SCREAMING_SNAKE_CASE	)
       UpperCAmelCase_				       =field(default_factory=__SCREAMING_SNAKE_CASE	)
       UpperCAmelCase_				       =None



       @classmethod
       def     _UpperCamelCase	(							cls ,     _A	)				->				List[str]:
          if name == "librispeech":
             return cls()
          if name == "timit":
             return cls(
                 do_lower_case=_A ,     translation_table=str.maketrans({'''-''': ''' '''}	) ,     )
          if name == "buckwalter":
             SCREAMING_SNAKE_CASE_	=      {
                 '''-''': ''' ''',  # sometimes used to represent pauses
                 '''^''': '''v''',  # fixing "tha" in arabic_speech_corpus dataset
             }
             return cls(
                 vocab_file=pathlib.Path(_A	).parent.joinpath('''vocab/buckwalter.json'''	) ,     word_delimiter_token='''/''' ,     translation_table=str.maketrans(_A	) ,     words_to_remove={'''sil'''} ,     untransliterator=arabic.buckwalter.untransliterate ,     )
          raise ValueError(F'''Unsupported orthography: \'{name}\'.'''	)



       def     _UpperCamelCase	(							self ,     _A	)				->				str:
          # TODO(elgeish) return a pipeline (e.g., from jiwer) instead? Or rely on branch predictor as is
          if len(self.translation_table	) > 0:
             SCREAMING_SNAKE_CASE_	=      text.translate(self.translation_table	)
          if len(self.words_to_remove	) == 0:
             SCREAMING_SNAKE_CASE_	=      ''' '''.join(text.split()	)  # clean up whitespaces
          else:
             SCREAMING_SNAKE_CASE_	=      ''' '''.join(w for w in text.split() if w not in self.words_to_remove	)  # and clean up whilespaces
          return text




       def     _UpperCamelCase	(							self ,     _A	)				->				WavaVecaProcessor:
          SCREAMING_SNAKE_CASE_	=      WavaVecaFeatureExtractor.from_pretrained(
              model_args.model_name_or_path ,     cache_dir=model_args.cache_dir	)
          if self.vocab_file:
             SCREAMING_SNAKE_CASE_	=      WavaVecaCTCTokenizer(
                 self.vocab_file ,     cache_dir=model_args.cache_dir ,     do_lower_case=self.do_lower_case ,     word_delimiter_token=self.word_delimiter_token ,     )
          else:
             SCREAMING_SNAKE_CASE_	=      WavaVecaCTCTokenizer.from_pretrained(
                 model_args.model_name_or_path ,     cache_dir=model_args.cache_dir ,     do_lower_case=self.do_lower_case ,     word_delimiter_token=self.word_delimiter_token ,     )
          return WavaVecaProcessor(_A ,     _A	)







@dataclass
class 				UpperCamelCase__		:






       """simple docstring"""


       UpperCAmelCase_				       =42
       UpperCAmelCase_				       =True
       UpperCAmelCase_				       =None
       UpperCAmelCase_				       =None
       UpperCAmelCase_				       =None
       UpperCAmelCase_				       =None



       def __call__(							self ,     _A	)				->				Dict[str, torch.Tensor]:
          # split inputs and labels since they have to be of different lenghts and need
          # different padding methods
          SCREAMING_SNAKE_CASE_	=      [{'''input_values''': feature['''input_values''']} for feature in features]
          SCREAMING_SNAKE_CASE_	=      [{'''input_ids''': feature['''labels''']} for feature in features]

          SCREAMING_SNAKE_CASE_	=      self.processor.pad(
              _A ,     padding=self.padding ,     max_length=self.max_length ,     pad_to_multiple_of=self.pad_to_multiple_of ,     return_tensors='''pt''' ,     )
          SCREAMING_SNAKE_CASE_	=      self.processor.pad(
              labels=_A ,     padding=self.padding ,     max_length=self.max_length_labels ,     pad_to_multiple_of=self.pad_to_multiple_of_labels ,     return_tensors='''pt''' ,     )

          # replace padding with -100 to ignore loss correctly
          SCREAMING_SNAKE_CASE_	=      labels_batch['''input_ids'''].masked_fill(labels_batch.attention_mask.ne(1	) ,     -100	)

          SCREAMING_SNAKE_CASE_	=      labels

          return batch







class 				UpperCamelCase__		(	__SCREAMING_SNAKE_CASE	):






       """simple docstring"""


       def     _UpperCamelCase	(							self ,     _A ,     _A	)				->				torch.Tensor:
          model.train()
          SCREAMING_SNAKE_CASE_	=      self._prepare_inputs(_A	)

          if self.use_amp:
             with autocast():
                SCREAMING_SNAKE_CASE_	=      self.compute_loss(_A ,     _A	)
          else:
             SCREAMING_SNAKE_CASE_	=      self.compute_loss(_A ,     _A	)

          if self.args.n_gpu > 1:
             if model.module.config.ctc_loss_reduction == "mean":
                SCREAMING_SNAKE_CASE_	=      loss.mean()
             elif model.module.config.ctc_loss_reduction == "sum":
                SCREAMING_SNAKE_CASE_	=      loss.sum() / (inputs['''labels'''] >= 0).sum()
             else:
                raise ValueError(F'''{model.config.ctc_loss_reduction} is not valid. Choose one of [\'mean\', \'sum\']'''	)

          if self.args.gradient_accumulation_steps > 1:
             SCREAMING_SNAKE_CASE_	=      loss / self.args.gradient_accumulation_steps

          if self.use_amp:
             self.scaler.scale(_A	).backward()
          elif self.use_apex:
             with amp.scale_loss(_A ,     self.optimizer	) as scaled_loss:
                scaled_loss.backward()
          elif self.deepspeed:
             self.deepspeed.backward(_A	)
          else:
             loss.backward()

          return loss.detach()







def  A__ (       ):
   # See all possible arguments in src/transformers/training_args.py
   # or by passing the --help flag to this script.
   # We now keep distinct sets of args, for a cleaner separation of concerns.

   SCREAMING_SNAKE_CASE_	=      HfArgumentParser((ModelArguments, DataTrainingArguments, TrainingArguments)						)

   SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	=      parser.parse_args_into_dataclasses()
   configure_logger(__lowerCamelCase,  __lowerCamelCase						)

   SCREAMING_SNAKE_CASE_	=      Orthography.from_name(data_args.orthography.lower()						)
   SCREAMING_SNAKE_CASE_	=      orthography.create_processor(__lowerCamelCase						)
   SCREAMING_SNAKE_CASE_	=      WavaVecaForCTC.from_pretrained(
       model_args.model_name_or_path,  cache_dir=model_args.cache_dir,  gradient_checkpointing=training_args.gradient_checkpointing,  vocab_size=len(processor.tokenizer						),  )

   SCREAMING_SNAKE_CASE_	=      datasets.load_dataset(
       data_args.dataset_name,  data_args.dataset_config_name,  split=data_args.train_split_name						)
   SCREAMING_SNAKE_CASE_	=      datasets.load_dataset(
       data_args.dataset_name,  data_args.dataset_config_name,  split=data_args.validation_split_name						)

   SCREAMING_SNAKE_CASE_	=      datasets.load_metric('''wer'''						)
   SCREAMING_SNAKE_CASE_	=      processor.feature_extractor.sampling_rate if data_args.target_feature_extractor_sampling_rate else None
   SCREAMING_SNAKE_CASE_	=      ''''''.join(t for t in processor.tokenizer.get_vocab().keys() if len(__lowerCamelCase						) == 1						)
   SCREAMING_SNAKE_CASE_	=      re.compile(  # remove characters not in vocabulary
       rF'''[^\s{re.escape(__lowerCamelCase						)}]''',  flags=re.IGNORECASE if processor.tokenizer.do_lower_case else 0,  )
   SCREAMING_SNAKE_CASE_	=      []

   def prepare_example(__lowerCamelCase						):  # TODO(elgeish) make use of multiprocessing?
      SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	=      librosa.load(example[data_args.speech_file_column],  sr=__lowerCamelCase						)
      if data_args.max_duration_in_seconds is not None:
         SCREAMING_SNAKE_CASE_	=      len(example['''speech''']						) / example['''sampling_rate''']
      # Normalize and clean up text; order matters!
      SCREAMING_SNAKE_CASE_	=      orthography.preprocess_for_training(example[data_args.target_text_column]						)
      SCREAMING_SNAKE_CASE_	=      vocabulary_text_cleaner.sub('''''',  __lowerCamelCase						)
      if updated_text != example[data_args.target_text_column]:
         text_updates.append((example[data_args.target_text_column], updated_text)						)
         SCREAMING_SNAKE_CASE_	=      updated_text
      return example

   SCREAMING_SNAKE_CASE_	=      train_dataset.map(__lowerCamelCase,  remove_columns=[data_args.speech_file_column]						)
   SCREAMING_SNAKE_CASE_	=      val_dataset.map(__lowerCamelCase,  remove_columns=[data_args.speech_file_column]						)

   if data_args.max_duration_in_seconds is not None:

      def filter_by_max_duration(__lowerCamelCase						):
         return example["duration_in_seconds"] <= data_args.max_duration_in_seconds

      SCREAMING_SNAKE_CASE_	=      len(__lowerCamelCase						)
      SCREAMING_SNAKE_CASE_	=      len(__lowerCamelCase						)
      SCREAMING_SNAKE_CASE_	=      train_dataset.filter(__lowerCamelCase,  remove_columns=['''duration_in_seconds''']						)
      SCREAMING_SNAKE_CASE_	=      val_dataset.filter(__lowerCamelCase,  remove_columns=['''duration_in_seconds''']						)
      if len(__lowerCamelCase						) > old_train_size:
         logger.warning(
             F'''Filtered out {len(__lowerCamelCase						) - old_train_size} train example(s) longer than'''
             F''' {data_args.max_duration_in_seconds} second(s).'''						)
      if len(__lowerCamelCase						) > old_val_size:
         logger.warning(
             F'''Filtered out {len(__lowerCamelCase						) - old_val_size} validation example(s) longer than'''
             F''' {data_args.max_duration_in_seconds} second(s).'''						)
   logger.info(F'''Split sizes: {len(__lowerCamelCase						)} train and {len(__lowerCamelCase						)} validation.'''						)

   logger.warning(F'''Updated {len(__lowerCamelCase						)} transcript(s) using \'{data_args.orthography}\' orthography rules.'''						)
   if logger.isEnabledFor(logging.DEBUG						):
      for original_text, updated_text in text_updates:
         logger.debug(F'''Updated text: "{original_text}" -> "{updated_text}"'''						)
   SCREAMING_SNAKE_CASE_	=      None

   def prepare_dataset(__lowerCamelCase						):
      # check that all files have the correct sampling rate
      assert (
          len(set(batch['''sampling_rate''']						)						) == 1
      ), F'''Make sure all inputs have the same sampling rate of {processor.feature_extractor.sampling_rate}.'''

      SCREAMING_SNAKE_CASE_	=      processor(
          audio=batch['''speech'''],  text=batch[data_args.target_text_column],  sampling_rate=batch['''sampling_rate'''][0]						)
      batch.update(__lowerCamelCase						)
      return batch

   SCREAMING_SNAKE_CASE_	=      train_dataset.map(
       __lowerCamelCase,  batch_size=training_args.per_device_train_batch_size,  batched=__lowerCamelCase,  num_proc=data_args.preprocessing_num_workers,  )
   SCREAMING_SNAKE_CASE_	=      val_dataset.map(
       __lowerCamelCase,  batch_size=training_args.per_device_train_batch_size,  batched=__lowerCamelCase,  num_proc=data_args.preprocessing_num_workers,  )

   SCREAMING_SNAKE_CASE_	=      DataCollatorCTCWithPadding(processor=__lowerCamelCase,  padding=__lowerCamelCase						)

   def compute_metrics(__lowerCamelCase						):
      SCREAMING_SNAKE_CASE_	=      pred.predictions
      SCREAMING_SNAKE_CASE_	=      np.argmax(__lowerCamelCase,  axis=-1						)

      SCREAMING_SNAKE_CASE_	=      processor.tokenizer.pad_token_id

      SCREAMING_SNAKE_CASE_	=      processor.batch_decode(__lowerCamelCase						)
      # we do not want to group tokens when computing the metrics
      SCREAMING_SNAKE_CASE_	=      processor.batch_decode(pred.label_ids,  group_tokens=__lowerCamelCase						)
      if logger.isEnabledFor(logging.DEBUG						):
         for reference, predicted in zip(__lowerCamelCase,  __lowerCamelCase						):
            logger.debug(F'''reference: "{reference}"'''						)
            logger.debug(F'''predicted: "{predicted}"'''						)
            if orthography.untransliterator is not None:
               logger.debug(F'''reference (untransliterated): "{orthography.untransliterator(__lowerCamelCase						)}"'''						)
               logger.debug(F'''predicted (untransliterated): "{orthography.untransliterator(__lowerCamelCase						)}"'''						)

      SCREAMING_SNAKE_CASE_	=      wer_metric.compute(predictions=__lowerCamelCase,  references=__lowerCamelCase						)

      return {"wer": wer}

   if model_args.freeze_feature_extractor:
      model.freeze_feature_extractor()

   SCREAMING_SNAKE_CASE_	=      CTCTrainer(
       model=__lowerCamelCase,  data_collator=__lowerCamelCase,  args=__lowerCamelCase,  compute_metrics=__lowerCamelCase,  train_dataset=__lowerCamelCase,  eval_dataset=__lowerCamelCase,  tokenizer=processor.feature_extractor,  )

   trainer.train()


if __name__ == "__main__":
   main()




from __future__ import annotations

from collections.abc import Iterable





class 				UpperCamelCase__		:






       """simple docstring"""


       def __init__(							self ,     _A ,     _A	)				->				Union[str, Any]:
          SCREAMING_SNAKE_CASE_	, SCREAMING_SNAKE_CASE_	=      float(_A	), float(_A	)



       def __eq__(							self ,     _A	)				->				str:
          return self.x == other.x and self.y == other.y



       def __ne__(							self ,     _A	)				->				Any:
          return not self == other



       def __gt__(							self ,     _A	)				->				List[Any]:
          if self.x > other.x:
             return True
          elif self.x == other.x:
             return self.y > other.y
          return False



       def __lt__(							self ,     _A	)				->				Optional[int]:
          return not self > other



       def __ge__(							self ,     _A	)				->				int:
          if self.x > other.x:
             return True
          elif self.x == other.x:
             return self.y >= other.y
          return False



       def __le__(							self ,     _A	)				->				str:
          if self.x < other.x:
             return True
          elif self.x == other.x:
             return self.y <= other.y
          return False



       def __repr__(							self	)				->				str:
          return F'''({self.x}, {self.y})'''




       def __hash__(							self	)				->				List[str]:
          return hash(self.x	)







def  A__ (       __lowerCamelCase,  ):
   SCREAMING_SNAKE_CASE_	=      []
   if list_of_tuples:
      for p in list_of_tuples:
         if isinstance(__lowerCamelCase,  __lowerCamelCase						):
            points.append(__lowerCamelCase						)
         else:
            try:
               points.append(Point(p[0],  p[1]						)						)
            except (IndexError, TypeError):
               print(
                   F'''Ignoring deformed point {p}. All points'''
                   ''' must have at least 2 coordinates.'''						)
   return points


def  A__ (       __lowerCamelCase						):

   if not hasattr(__lowerCamelCase,  '''__iter__'''						):
      SCREAMING_SNAKE_CASE_	=      F'''Expecting an iterable object but got an non-iterable type {points}'''
      raise ValueError(__lowerCamelCase						)

   if not points:
      SCREAMING_SNAKE_CASE_	=      F'''Expecting a list of points but got {points}'''
      raise ValueError(__lowerCamelCase						)

   return _construct_points(__lowerCamelCase						)


def  A__ (       __lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase						):
   SCREAMING_SNAKE_CASE_	=      (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x)
   return det


def  A__ (       __lowerCamelCase						):
   SCREAMING_SNAKE_CASE_	=      sorted(_validate_input(__lowerCamelCase						)						)
   SCREAMING_SNAKE_CASE_	=      len(__lowerCamelCase						)
   SCREAMING_SNAKE_CASE_	=      set()

   for i in range(n - 1						):
      for j in range(i + 1,  __lowerCamelCase						):
         SCREAMING_SNAKE_CASE_	=      SCREAMING_SNAKE_CASE_	=      False
         SCREAMING_SNAKE_CASE_	=      True
         for k in range(__lowerCamelCase						):
            if k != i and k != j:
               SCREAMING_SNAKE_CASE_	=      _det(points[i],  points[j],  points[k]						)

               if det_k > 0:
                  SCREAMING_SNAKE_CASE_	=      True
               elif det_k < 0:
                  SCREAMING_SNAKE_CASE_	=      True
               else:
                  # point[i], point[j], point[k] all lie on a straight line
                  # if point[k] is to the left of point[i] or it's to the
                  # right of point[j], then point[i], point[j] cannot be
                  # part of the convex hull of A
                  if points[k] < points[i] or points[k] > points[j]:
                     SCREAMING_SNAKE_CASE_	=      False
                     break

            if points_left_of_ij and points_right_of_ij:
               SCREAMING_SNAKE_CASE_	=      False
               break

         if ij_part_of_convex_hull:
            convex_set.update([points[i], points[j]]						)

   return sorted(__lowerCamelCase						)


def  A__ (       __lowerCamelCase						):
   SCREAMING_SNAKE_CASE_	=      sorted(_validate_input(__lowerCamelCase						)						)
   SCREAMING_SNAKE_CASE_	=      len(__lowerCamelCase						)

   # divide all the points into an upper hull and a lower hull
   # the left most point and the right most point are definitely
   # members of the convex hull by definition.
   # use these two anchors to divide all the points into two hulls,
   # an upper hull and a lower hull.

   # all points to the left (above) the line joining the extreme points belong to the
   # upper hull
   # all points to the right (below) the line joining the extreme points below to the
   # lower hull
   # ignore all points on the line joining the extreme points since they cannot be
   # part of the convex hull

   SCREAMING_SNAKE_CASE_	=      points[0]
   SCREAMING_SNAKE_CASE_	=      points[n - 1]

   SCREAMING_SNAKE_CASE_	=      {left_most_point, right_most_point}
   SCREAMING_SNAKE_CASE_	=      []
   SCREAMING_SNAKE_CASE_	=      []

   for i in range(1,  n - 1						):
      SCREAMING_SNAKE_CASE_	=      _det(__lowerCamelCase,  __lowerCamelCase,  points[i]						)

      if det > 0:
         upper_hull.append(points[i]						)
      elif det < 0:
         lower_hull.append(points[i]						)

   _construct_hull(__lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase						)
   _construct_hull(__lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase						)

   return sorted(__lowerCamelCase						)


def  A__ (       __lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase						):
   if points:
      SCREAMING_SNAKE_CASE_	=      None
      SCREAMING_SNAKE_CASE_	=      float('''-inf'''						)
      SCREAMING_SNAKE_CASE_	=      []

      for p in points:
         SCREAMING_SNAKE_CASE_	=      _det(__lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase						)

         if det > 0:
            candidate_points.append(__lowerCamelCase						)

            if det > extreme_point_distance:
               SCREAMING_SNAKE_CASE_	=      det
               SCREAMING_SNAKE_CASE_	=      p

      if extreme_point:
         _construct_hull(__lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase						)
         convex_set.add(__lowerCamelCase						)
         _construct_hull(__lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase,  __lowerCamelCase						)


def  A__ (       __lowerCamelCase						):
   SCREAMING_SNAKE_CASE_	=      sorted(_validate_input(__lowerCamelCase						)						)
   SCREAMING_SNAKE_CASE_	=      len(__lowerCamelCase						)

   SCREAMING_SNAKE_CASE_	=      points[:2]
   for i in range(2,  __lowerCamelCase						):
      SCREAMING_SNAKE_CASE_	=      _det(convex_hull[1],  convex_hull[0],  points[i]						)
      if det > 0:
         convex_hull.insert(0,  points[i]						)
         break
      elif det < 0:
         convex_hull.append(points[i]						)
         break
      else:
         SCREAMING_SNAKE_CASE_	=      points[i]
   i += 1

   for j in range(__lowerCamelCase,  __lowerCamelCase						):
      if (
          _det(convex_hull[0],  convex_hull[-1],  points[j]						) > 0
          and _det(convex_hull[-1],  convex_hull[0],  points[1]						) < 0
      ):
         # The point lies within the convex hull
         continue

      convex_hull.insert(0,  points[j]						)
      convex_hull.append(points[j]						)
      while _det(convex_hull[0],  convex_hull[1],  convex_hull[2]						) >= 0:
         del convex_hull[1]
      while _det(convex_hull[-1],  convex_hull[-2],  convex_hull[-3]						) <= 0:
         del convex_hull[-2]

    # `convex_hull` is contains the convex hull in circular order
   return sorted(convex_hull[1:] if len(__lowerCamelCase						) > 3 else convex_hull						)


def  A__ (       ):
   SCREAMING_SNAKE_CASE_	=      [
       (0, 3),
       (2, 2),
       (1, 1),
       (2, 1),
       (3, 0),
       (0, 0),
       (3, 3),
       (2, -1),
       (2, -4),
       (1, -3),
   ]
   # the convex set of points is
   # [(0, 0), (0, 3), (1, -3), (2, -4), (3, 0), (3, 3)]
   SCREAMING_SNAKE_CASE_	=      convex_hull_bf(__lowerCamelCase						)

   SCREAMING_SNAKE_CASE_	=      convex_hull_recursive(__lowerCamelCase						)
   assert results_bf == results_recursive

   SCREAMING_SNAKE_CASE_	=      convex_hull_melkman(__lowerCamelCase						)
   assert results_bf == results_melkman

   print(__lowerCamelCase						)


if __name__ == "__main__":
   main()


