






import json
import os
from functools import lru_cache
from typing import TYPE_CHECKING, List, Optional, Tuple, Union

import numpy as np
import regex as re

from ...utils import is_tf_available, is_torch_available, logging


if TYPE_CHECKING:
       if is_torch_available():
              import torch
       if is_tf_available():
              import tensorflow as tf

from ...tokenization_utils import AddedToken, PreTrainedTokenizer


UpperCamelCase											=      logging.get_logger(__name__)

UpperCamelCase											=      {
    '''vocab_file''': '''vocab.json''',
    '''merges_file''': '''merges.txt''',
}

UpperCamelCase											=      {
    '''vocab_file''': {
        '''Salesforce/codegen-350M-mono''': '''https://huggingface.co/Salesforce/codegen-350M-mono/resolve/main/vocab.json''',
    },
    '''merges_file''': {
        '''Salesforce/codegen-350M-mono''': '''https://huggingface.co/Salesforce/codegen-350M-mono/resolve/main/merges.txt''',
    },
}

UpperCamelCase											=      {
    '''Salesforce/codegen-350M-mono''': 2_0_4_8,
}




@lru_cache()
def       _a   (							)  ->      Tuple:
 lowerCamelCase_							:    int							=     (
     list(range(ord('!'				) ,			ord('~'				) + 1				)				) + list(range(ord('¡'				) ,			ord('¬'				) + 1				)				) + list(range(ord('®'				) ,			ord('ÿ'				) + 1				)				)
 )
 lowerCamelCase_							:    Tuple							=     bs[:]
 lowerCamelCase_							:    List[Any]							=     0
 for b in range(2**8				):
  if b not in bs:
   bs.append(lowerCamelCase__				)
   cs.append(2**8 + n				)
   n += 1
 lowerCamelCase_							:    List[Any]							=     [chr(lowerCamelCase__				) for n in cs]
 return dict(zip(lowerCamelCase__ ,			lowerCamelCase__				)				)




def       _a   (							lowerCamelCase__				)  ->      int:
 lowerCamelCase_							:    Tuple							=     set()
 lowerCamelCase_							:    List[str]							=     word[0]
 for char in word[1:]:
  pairs.add((prev_char, char)				)
  lowerCamelCase_							:    Optional[Any]							=     char
 return pairs





class 	lowerCamelCase__				(							UpperCAmelCase ):
      lowerCamelCase_							:   Optional[Any]											=	VOCAB_FILES_NAMES
      lowerCamelCase_							:   Union[str, Any]											=	PRETRAINED_VOCAB_FILES_MAP
      lowerCamelCase_							:   Any											=	PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
      lowerCamelCase_							:   Dict											=	['input_ids', 'attention_mask']






      def __init__(self					:    int		,		_snake_case					:    Any		,		_snake_case					:    str		,		_snake_case					:    Union[str, Any]="replace"		,		_snake_case					:    List[str]="<|endoftext|>"		,		_snake_case					:    Optional[int]="<|endoftext|>"		,		_snake_case					:    Optional[int]="<|endoftext|>"		,		_snake_case					:    Optional[Any]=None		,		_snake_case					:    Union[str, Any]=False		,		_snake_case					:    Union[str, Any]=False		,		**_snake_case					:    Any		,		)       ->   List[Any]:


       """simple docstring"""






       lowerCamelCase_							:    Union[str, Any]							=     AddedToken(_snake_case		,		lstrip=_snake_case		,		rstrip=_snake_case		) if isinstance(_snake_case		,		_snake_case		) else bos_token
       lowerCamelCase_							:    List[str]							=     AddedToken(_snake_case		,		lstrip=_snake_case		,		rstrip=_snake_case		) if isinstance(_snake_case		,		_snake_case		) else eos_token
       lowerCamelCase_							:    Union[str, Any]							=     AddedToken(_snake_case		,		lstrip=_snake_case		,		rstrip=_snake_case		) if isinstance(_snake_case		,		_snake_case		) else unk_token
       lowerCamelCase_							:    Tuple							=     AddedToken(_snake_case		,		lstrip=_snake_case		,		rstrip=_snake_case		) if isinstance(_snake_case		,		_snake_case		) else pad_token
       super().__init__(
           errors=_snake_case		,		unk_token=_snake_case		,		bos_token=_snake_case		,		eos_token=_snake_case		,		pad_token=_snake_case		,		add_prefix_space=_snake_case		,		add_bos_token=_snake_case		,		**_snake_case		,		)
       lowerCamelCase_							:    int							=     add_bos_token

       with open(_snake_case		,		encoding='utf-8'		) as vocab_handle:
        lowerCamelCase_							:    int							=     json.load(_snake_case		)
       lowerCamelCase_							:    Optional[int]							=     {v: k for k, v in self.encoder.items()}
       lowerCamelCase_							:    Dict							=     errors  # how to handle errors in decoding
       lowerCamelCase_							:    int							=     bytes_to_unicode()
       lowerCamelCase_							:    Optional[int]							=     {v: k for k, v in self.byte_encoder.items()}
       with open(_snake_case		,		encoding='utf-8'		) as merges_handle:
        lowerCamelCase_							:    str							=     merges_handle.read().split('\n'		)[1:-1]
       lowerCamelCase_							:    int							=     [tuple(merge.split()		) for merge in bpe_merges]
       lowerCamelCase_							:    int							=     dict(zip(_snake_case		,		range(len(_snake_case		)		)		)		)
       lowerCamelCase_							:    Optional[Any]							=     {}
       lowerCamelCase_							:    Optional[int]							=     add_prefix_space

       # Should have added re.IGNORECASE so BPE merges can happen for capitalized versions of contractions
       lowerCamelCase_							:    Union[str, Any]							=     re.compile(R'\'s|\'t|\'re|\'ve|\'m|\'ll|\'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+'		)






      @property
      def      UpperCAmelCase_     (self					:    Any		)       ->   Any:


       """simple docstring"""






       return len(self.encoder		)






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


       """simple docstring"""






       return dict(self.encoder		,		**self.added_tokens_encoder		)






      def      UpperCAmelCase_     (self					:    Optional[int]		,		_snake_case					:    Any		)       ->   Optional[Any]:


       """simple docstring"""






       if token in self.cache:
        return self.cache[token]
       lowerCamelCase_							:    Optional[Any]							=     tuple(_snake_case		)
       lowerCamelCase_							:    List[str]							=     get_pairs(_snake_case		)

       if not pairs:
        return token

       while True:
        lowerCamelCase_							:    str							=     min(_snake_case		,		key=lambda _snake_case		: self.bpe_ranks.get(_snake_case		,		float('inf'		)		)		)
        if bigram not in self.bpe_ranks:
         break
        lowerCamelCase_		,      lowerCamelCase_							:    Union[str, Any]							=     bigram
        lowerCamelCase_							:    Any							=     []
        lowerCamelCase_							:    Union[str, Any]							=     0
        while i < len(_snake_case		):
         try:
          lowerCamelCase_							:    Optional[int]							=     word.index(_snake_case		,		_snake_case		)
         except ValueError:
          new_word.extend(word[i:]		)
          break
         else:
          new_word.extend(word[i:j]		)
          lowerCamelCase_							:    str							=     j

         if word[i] == first and i < len(_snake_case		) - 1 and word[i + 1] == second:
          new_word.append(first + second		)
          i += 2
         else:
          new_word.append(word[i]		)
          i += 1
        lowerCamelCase_							:    Union[str, Any]							=     tuple(_snake_case		)
        lowerCamelCase_							:    Union[str, Any]							=     new_word
        if len(_snake_case		) == 1:
         break
        else:
         lowerCamelCase_							:    Union[str, Any]							=     get_pairs(_snake_case		)
       lowerCamelCase_							:    Optional[int]							=     ' '.join(_snake_case		)
       lowerCamelCase_							:    int							=     word
       return word






      def      UpperCAmelCase_     (self					:    str		,		_snake_case					:    Any		,		_snake_case					:    List[Any]=None		)       ->   str:


       """simple docstring"""






       if self.add_bos_token:
        lowerCamelCase_							:    List[Any]							=     [self.bos_token_id]
       else:
        lowerCamelCase_							:    Tuple							=     []

       lowerCamelCase_							:    Optional[Any]							=     bos_token_ids + token_ids_a

       if token_ids_a is None:
        return output

       return output + bos_token_ids + token_ids_a






      def      UpperCAmelCase_     (self					:    Tuple		,		_snake_case					:    Optional[int]		)       ->   Optional[int]:


       """simple docstring"""






       lowerCamelCase_							:    Dict							=     []
       for token in re.findall(self.pat		,		_snake_case		):
        lowerCamelCase_							:    List[Any]							=     ''.join(
            self.byte_encoder[b] for b in token.encode('utf-8'		)		)  # Maps all our bytes to unicode strings, avoiding control tokens of the BPE (spaces in our case)
        bpe_tokens.extend(bpe_token for bpe_token in self.bpe(_snake_case		).split(' '		)		)
       return bpe_tokens






      def      UpperCAmelCase_     (self					:    Tuple		,		_snake_case					:    int		)       ->   List[str]:


       """simple docstring"""






       return self.encoder.get(_snake_case		,		self.encoder.get(self.unk_token		)		)






      def      UpperCAmelCase_     (self					:    Optional[Any]		,		_snake_case					:    List[str]		)       ->   Tuple:


       """simple docstring"""






       return self.decoder.get(_snake_case		)






      def      UpperCAmelCase_     (self					:    str		,		_snake_case					:    List[str]		)       ->   Optional[Any]:


       """simple docstring"""






       lowerCamelCase_							:    str							=     ''.join(_snake_case		)
       lowerCamelCase_							:    str							=     bytearray([self.byte_decoder[c] for c in text]		).decode('utf-8'		,		errors=self.errors		)
       return text






      def      UpperCAmelCase_     (self					:    Union[str, Any]		,		_snake_case					:    str		,		_snake_case					:    Optional[str] = None		)       ->   Tuple[str]:


       """simple docstring"""






       if not os.path.isdir(_snake_case		):
        logger.error(f'Vocabulary path ({save_directory}) should be a directory'		)
        return
       lowerCamelCase_							:    List[str]							=     os.path.join(
           _snake_case		,		(filename_prefix + '-' if filename_prefix else '') + VOCAB_FILES_NAMES['vocab_file']		)
       lowerCamelCase_							:    Optional[Any]							=     os.path.join(
           _snake_case		,		(filename_prefix + '-' if filename_prefix else '') + VOCAB_FILES_NAMES['merges_file']		)

       with open(_snake_case		,		'w'		,		encoding='utf-8'		) as f:
        f.write(json.dumps(self.encoder		,		indent=2		,		sort_keys=_snake_case		,		ensure_ascii=_snake_case		) + '\n'		)

       lowerCamelCase_							:    Union[str, Any]							=     0
       with open(_snake_case		,		'w'		,		encoding='utf-8'		) as writer:
        writer.write('#version: 0.2\n'		)
        for bpe_tokens, token_index in sorted(self.bpe_ranks.items()		,		key=lambda _snake_case		: kv[1]		):
         if index != token_index:
          logger.warning(
              f'Saving vocabulary to {merge_file}: BPE merge indices are not consecutive.'
              ' Please check that the tokenizer is not corrupted!'		)
          lowerCamelCase_							:    Optional[int]							=     token_index
         writer.write(' '.join(_snake_case		) + '\n'		)
         index += 1

       return vocab_file, merge_file






      def      UpperCAmelCase_     (self					:    List[str]		,		_snake_case					:    Dict		,		_snake_case					:    List[Any]=False		,		**_snake_case					:    Any		)       ->   Optional[int]:


       """simple docstring"""






       lowerCamelCase_							:    List[str]							=     kwargs.pop('add_prefix_space'		,		self.add_prefix_space		)
       if is_split_into_words or add_prefix_space:
        lowerCamelCase_							:    Optional[int]							=     ' ' + text
       return (text, kwargs)






      def      UpperCAmelCase_     (self					:    str		,		_snake_case					:    Union[int, List[int], "np.ndarray", "torch.Tensor", "tf.Tensor"]		,		_snake_case					:    bool = False		,		_snake_case					:    bool = None		,		_snake_case					:    Optional[List[str]] = None		,		**_snake_case					:    Optional[Any]		,		)       ->   str:


       """simple docstring"""






       lowerCamelCase_							:    Optional[int]							=     super()._decode(
           token_ids=_snake_case		,		skip_special_tokens=_snake_case		,		clean_up_tokenization_spaces=_snake_case		,		**_snake_case		,		)

       if truncate_before_pattern is not None and len(_snake_case		) > 0:
        lowerCamelCase_							:    str							=     self.truncate(_snake_case		,		_snake_case		)

       return decoded_text






      def      UpperCAmelCase_     (self					:    Dict		,		_snake_case					:    str		,		_snake_case					:    int		)       ->   Dict:


       """simple docstring"""






       def find_re(_snake_case					:    List[str]		,		_snake_case					:    Optional[Any]		,		_snake_case					:    str		):
        lowerCamelCase_							:    List[Any]							=     pattern.search(_snake_case		,		_snake_case		)
        return m.start() if m else -1

       lowerCamelCase_							:    List[str]							=     [re.compile(_snake_case		,		re.MULTILINE		) for pattern in truncate_before_pattern]

       lowerCamelCase_							:    Optional[int]							=     list(re.finditer('^print'		,		_snake_case		,		re.MULTILINE		)		)

       if len(_snake_case		) > 1:
        lowerCamelCase_							:    Any							=     completion[: prints[1].start()]

       lowerCamelCase_							:    Any							=     list(re.finditer('^def'		,		_snake_case		,		re.MULTILINE		)		)

       if len(_snake_case		) > 1:
        lowerCamelCase_							:    Dict							=     completion[: defs[1].start()]

       lowerCamelCase_							:    int							=     0

       lowerCamelCase_							:    Tuple							=     [
           pos for pos in [find_re(_snake_case		,		_snake_case		,		_snake_case		) for terminal in terminals] if pos != -1
       ]

       if len(_snake_case		) > 0:
        return completion[: min(_snake_case		)]
       else:
        return completion








import math




class 	lowerCamelCase__				:






      def __init__(self					:    int		,		_snake_case					:    Dict		)       ->   Union[str, Any]:


       """simple docstring"""






       lowerCamelCase_							:    Optional[Any]							=     len(_snake_case		)
       lowerCamelCase_							:    Optional[Any]							=     [0] * (
           4 * self.N
       )  # approximate the overall size of segment tree with array N
       self.build(1		,		0		,		self.N - 1		)






      def      UpperCAmelCase_     (self					:    List[str]		,		_snake_case					:    List[str]		)       ->   int:


       """simple docstring"""






       return idx * 2






      def      UpperCAmelCase_     (self					:    Tuple		,		_snake_case					:    Dict		)       ->   Optional[Any]:


       """simple docstring"""






       return idx * 2 + 1






      def      UpperCAmelCase_     (self					:    List[Any]		,		_snake_case					:    List[Any]		,		_snake_case					:    str		,		_snake_case					:    List[Any]		)       ->   Optional[Any]:  # noqa: E741


       """simple docstring"""






       if l == r:
        lowerCamelCase_							:    List[Any]							=     A[l]
       else:
        lowerCamelCase_							:    int							=     (l + r) // 2
        self.build(self.left(_snake_case		)		,		_snake_case		,		_snake_case		)
        self.build(self.right(_snake_case		)		,		mid + 1		,		_snake_case		)
        lowerCamelCase_							:    Tuple							=     max(self.st[self.left(_snake_case		)]		,		self.st[self.right(_snake_case		)]		)






      def      UpperCAmelCase_     (self					:    str		,		_snake_case					:    Tuple		,		_snake_case					:    Any		,		_snake_case					:    str		)       ->   Tuple:


       """simple docstring"""






       return self.update_recursive(1		,		0		,		self.N - 1		,		a - 1		,		b - 1		,		_snake_case		)






      def      UpperCAmelCase_     (self					:    Tuple		,		_snake_case					:    List[str]		,		_snake_case					:    Tuple		,		_snake_case					:    Optional[int]		,		_snake_case					:    int		,		_snake_case					:    Tuple		,		_snake_case					:    List[str]		)       ->   Optional[Any]:  # noqa: E741


       """simple docstring"""






       if r < a or l > b:
        return True
       if l == r:
        lowerCamelCase_							:    Tuple							=     val
        return True
       lowerCamelCase_							:    Optional[int]							=     (l + r) // 2
       self.update_recursive(self.left(_snake_case		)		,		_snake_case		,		_snake_case		,		_snake_case		,		_snake_case		,		_snake_case		)
       self.update_recursive(self.right(_snake_case		)		,		mid + 1		,		_snake_case		,		_snake_case		,		_snake_case		,		_snake_case		)
       lowerCamelCase_							:    Union[str, Any]							=     max(self.st[self.left(_snake_case		)]		,		self.st[self.right(_snake_case		)]		)
       return True






      def      UpperCAmelCase_     (self					:    List[Any]		,		_snake_case					:    List[Any]		,		_snake_case					:    Optional[int]		)       ->   str:


       """simple docstring"""






       return self.query_recursive(1		,		0		,		self.N - 1		,		a - 1		,		b - 1		)






      def      UpperCAmelCase_     (self					:    Any		,		_snake_case					:    List[Any]		,		_snake_case					:    Optional[Any]		,		_snake_case					:    int		,		_snake_case					:    Optional[int]		,		_snake_case					:    Optional[Any]		)       ->   str:  # noqa: E741


       """simple docstring"""






       if r < a or l > b:
        return -math.inf
       if l >= a and r <= b:
        return self.st[idx]
       lowerCamelCase_							:    int							=     (l + r) // 2
       lowerCamelCase_							:    Optional[Any]							=     self.query_recursive(self.left(_snake_case		)		,		_snake_case		,		_snake_case		,		_snake_case		,		_snake_case		)
       lowerCamelCase_							:    Union[str, Any]							=     self.query_recursive(self.right(_snake_case		)		,		mid + 1		,		_snake_case		,		_snake_case		,		_snake_case		)
       return max(_snake_case		,		_snake_case		)






      def      UpperCAmelCase_     (self					:    str		)       ->   Tuple:


       """simple docstring"""






       lowerCamelCase_							:    Dict							=     []
       for i in range(1		,		N + 1		):
        show_list += [self.query(_snake_case		,		_snake_case		)]
       print(_snake_case		)


if __name__ == "__main__":
       UpperCamelCase											=      [1, 2, -4, 7, 3, -5, 6, 1_1, -2_0, 9, 1_4, 1_5, 5, 2, -8]
       UpperCamelCase											=      1_5
       UpperCamelCase											=      SegmentTree(A)
       print(segt.query(4, 6))
       print(segt.query(7, 1_1))
       print(segt.query(7, 1_2))
       segt.update(1, 3, 1_1_1)
       print(segt.query(1, 1_5))
       segt.update(7, 8, 2_3_5)
       segt.show_data()
