


"""simple docstring"""




import os
import unicodedata
from shutil import copyfile
from typing import Any, Dict, List, Optional, Tuple

import sentencepiece as spm

from ...tokenization_utils import AddedToken, PreTrainedTokenizer
from ...utils import logging


lowerCamelCase						=		logging.get_logger(__name__)
lowerCamelCase						=		{'''vocab_file''': '''spiece.model'''}

lowerCamelCase						=		{
    '''vocab_file''': {
        '''albert-base-v1''': '''https://huggingface.co/albert-base-v1/resolve/main/spiece.model''',
        '''albert-large-v1''': '''https://huggingface.co/albert-large-v1/resolve/main/spiece.model''',
        '''albert-xlarge-v1''': '''https://huggingface.co/albert-xlarge-v1/resolve/main/spiece.model''',
        '''albert-xxlarge-v1''': '''https://huggingface.co/albert-xxlarge-v1/resolve/main/spiece.model''',
        '''albert-base-v2''': '''https://huggingface.co/albert-base-v2/resolve/main/spiece.model''',
        '''albert-large-v2''': '''https://huggingface.co/albert-large-v2/resolve/main/spiece.model''',
        '''albert-xlarge-v2''': '''https://huggingface.co/albert-xlarge-v2/resolve/main/spiece.model''',
        '''albert-xxlarge-v2''': '''https://huggingface.co/albert-xxlarge-v2/resolve/main/spiece.model''',
    }
}

lowerCamelCase						=		{
    '''albert-base-v1''': 512,
    '''albert-large-v1''': 512,
    '''albert-xlarge-v1''': 512,
    '''albert-xxlarge-v1''': 512,
    '''albert-base-v2''': 512,
    '''albert-large-v2''': 512,
    '''albert-xlarge-v2''': 512,
    '''albert-xxlarge-v2''': 512,
}

lowerCamelCase						=		'''▁'''





class  _a							(    snake_case_):
	_a  :  Dict				   =							VOCAB_FILES_NAMES
	_a  :  Optional[Any]				   =							PRETRAINED_VOCAB_FILES_MAP
	_a  :  Tuple				   =							PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES




	def __init__( self						:		int		, _SCREAMING_SNAKE_CASE						:		Any		, _SCREAMING_SNAKE_CASE						:		Union[str, Any]=True		, _SCREAMING_SNAKE_CASE						:		int=True		, _SCREAMING_SNAKE_CASE						:		Optional[int]=False		, _SCREAMING_SNAKE_CASE						:		int="[CLS]"		, _SCREAMING_SNAKE_CASE						:		List[str]="[SEP]"		, _SCREAMING_SNAKE_CASE						:		Optional[int]="<unk>"		, _SCREAMING_SNAKE_CASE						:		str="[SEP]"		, _SCREAMING_SNAKE_CASE						:		List[str]="<pad>"		, _SCREAMING_SNAKE_CASE						:		Dict="[CLS]"		, _SCREAMING_SNAKE_CASE						:		Any="[MASK]"		, _SCREAMING_SNAKE_CASE						:		Optional[Dict[str, Any]] = None		, **_SCREAMING_SNAKE_CASE						:		Optional[Any]		, )->	None:
			lowerCAmelCase__       :      Optional[int]   					= (
			    AddedToken(_SCREAMING_SNAKE_CASE		, lstrip=_SCREAMING_SNAKE_CASE		, rstrip=_SCREAMING_SNAKE_CASE		, normalized=_SCREAMING_SNAKE_CASE		)
			    if isinstance(_SCREAMING_SNAKE_CASE		, _SCREAMING_SNAKE_CASE		)
			    else mask_token
			)

			lowerCAmelCase__       :      Optional[Any]   					= {} if sp_model_kwargs is None else sp_model_kwargs

			super().__init__(
			    do_lower_case=_SCREAMING_SNAKE_CASE		, remove_space=_SCREAMING_SNAKE_CASE		, keep_accents=_SCREAMING_SNAKE_CASE		, bos_token=_SCREAMING_SNAKE_CASE		, eos_token=_SCREAMING_SNAKE_CASE		, unk_token=_SCREAMING_SNAKE_CASE		, sep_token=_SCREAMING_SNAKE_CASE		, pad_token=_SCREAMING_SNAKE_CASE		, cls_token=_SCREAMING_SNAKE_CASE		, mask_token=_SCREAMING_SNAKE_CASE		, sp_model_kwargs=self.sp_model_kwargs		, **_SCREAMING_SNAKE_CASE		, )

			lowerCAmelCase__       :      Optional[int]   					= do_lower_case
			lowerCAmelCase__       :      Union[str, Any]   					= remove_space
			lowerCAmelCase__       :      Any   					= keep_accents
			lowerCAmelCase__       :      Dict   					= vocab_file

			lowerCAmelCase__       :      Any   					= spm.SentencePieceProcessor(**self.sp_model_kwargs		)
			self.sp_model.Load(_SCREAMING_SNAKE_CASE		)




	@property
	def 							UpperCAmelCase__( self						:		Tuple		)->	Any:
			return len(self.sp_model		)




	def 							UpperCAmelCase__( self						:		Optional[int]		)->	Tuple:
			lowerCAmelCase__       :      Dict   					= {self.convert_ids_to_tokens(_SCREAMING_SNAKE_CASE		): i for i in range(self.vocab_size		)}
			vocab.update(self.added_tokens_encoder		)
			return vocab




	def __getstate__( self						:		Tuple		)->	List[Any]:
			lowerCAmelCase__       :      Optional[int]   					= self.__dict__.copy()
			lowerCAmelCase__       :      List[str]   					= None
			return state




	def __setstate__( self						:		Tuple		, _SCREAMING_SNAKE_CASE						:		Optional[int]		)->	Tuple:
			lowerCAmelCase__       :      Any   					= d

			# for backward compatibility
			if not hasattr(self		, '''sp_model_kwargs'''		):
					lowerCAmelCase__       :      List[Any]   					= {}

			lowerCAmelCase__       :      List[str]   					= spm.SentencePieceProcessor(**self.sp_model_kwargs		)
			self.sp_model.Load(self.vocab_file		)




	def 							UpperCAmelCase__( self						:		List[str]		, _SCREAMING_SNAKE_CASE						:		Dict		)->	List[Any]:





			if self.remove_space:
					lowerCAmelCase__       :      Tuple   					= ' '.join(inputs.strip().split()		)
			else:
					lowerCAmelCase__       :      Union[str, Any]   					= inputs
			lowerCAmelCase__       :      Tuple   					= outputs.replace('''``'''		, '''"'''		).replace('''\'\''''		, '''"'''		)

			if not self.keep_accents:
					lowerCAmelCase__       :      Union[str, Any]   					= unicodedata.normalize('''NFKD'''		, _SCREAMING_SNAKE_CASE		)
					lowerCAmelCase__       :      Union[str, Any]   					= ''.join([c for c in outputs if not unicodedata.combining(_SCREAMING_SNAKE_CASE		)]		)
			if self.do_lower_case:
					lowerCAmelCase__       :      int   					= outputs.lower()

			return outputs




	def 							UpperCAmelCase__( self						:		int		, _SCREAMING_SNAKE_CASE						:		str		)->	List[str]:
			lowerCAmelCase__       :      List[str]   					= self.preprocess_text(_SCREAMING_SNAKE_CASE		)
			lowerCAmelCase__       :      List[Any]   					= self.sp_model.encode(_SCREAMING_SNAKE_CASE		, out_type=_SCREAMING_SNAKE_CASE		)
			lowerCAmelCase__       :      Optional[Any]   					= []
			for piece in pieces:
					if len(_SCREAMING_SNAKE_CASE		) > 1 and piece[-1] == str(''','''		) and piece[-2].isdigit():
							lowerCAmelCase__       :      str   					= self.sp_model.EncodeAsPieces(piece[:-1].replace(_SCREAMING_SNAKE_CASE		, ''''''		)		)
							if piece[0] != SPIECE_UNDERLINE and cur_pieces[0][0] == SPIECE_UNDERLINE:
									if len(cur_pieces[0]		) == 1:
											lowerCAmelCase__       :      Optional[int]   					= cur_pieces[1:]
									else:
											lowerCAmelCase__       :      Union[str, Any]   					= cur_pieces[0][1:]
							cur_pieces.append(piece[-1]		)
							new_pieces.extend(_SCREAMING_SNAKE_CASE		)
					else:
							new_pieces.append(_SCREAMING_SNAKE_CASE		)

			return new_pieces




	def 							UpperCAmelCase__( self						:		str		, _SCREAMING_SNAKE_CASE						:		List[Any]		)->	Tuple:
			return self.sp_model.PieceToId(_SCREAMING_SNAKE_CASE		)




	def 							UpperCAmelCase__( self						:		Dict		, _SCREAMING_SNAKE_CASE						:		Union[str, Any]		)->	List[Any]:
			return self.sp_model.IdToPiece(_SCREAMING_SNAKE_CASE		)




	def 							UpperCAmelCase__( self						:		Optional[Any]		, _SCREAMING_SNAKE_CASE						:		List[str]		)->	Tuple:
			lowerCAmelCase__       :      Any   					= []
			lowerCAmelCase__       :      Dict   					= ''
			lowerCAmelCase__       :      List[str]   					= False
			for token in tokens:
					# make sure that special tokens are not decoded using sentencepiece model
					if token in self.all_special_tokens:
							if not prev_is_special:
									out_string += " "
							out_string += self.sp_model.decode(_SCREAMING_SNAKE_CASE		) + token
							lowerCAmelCase__       :      Dict   					= True
							lowerCAmelCase__       :      Any   					= []
					else:
							current_sub_tokens.append(_SCREAMING_SNAKE_CASE		)
							lowerCAmelCase__       :      Dict   					= False
			out_string += self.sp_model.decode(_SCREAMING_SNAKE_CASE		)
			return out_string.strip()




	def 							UpperCAmelCase__( self						:		List[str]		, _SCREAMING_SNAKE_CASE						:		List[int]		, _SCREAMING_SNAKE_CASE						:		Optional[List[int]] = None		)->	List[int]:
			lowerCAmelCase__       :      Optional[int]   					= [self.sep_token_id]
			lowerCAmelCase__       :      Tuple   					= [self.cls_token_id]
			if token_ids_a is None:
					return cls + token_ids_a + sep
			return cls + token_ids_a + sep + token_ids_a + sep




	def 							UpperCAmelCase__( self						:		Tuple		, _SCREAMING_SNAKE_CASE						:		List[int]		, _SCREAMING_SNAKE_CASE						:		Optional[List[int]] = None		, _SCREAMING_SNAKE_CASE						:		bool = False		)->	List[int]:





			if already_has_special_tokens:
					return super().get_special_tokens_mask(
					    token_ids_a=_SCREAMING_SNAKE_CASE		, token_ids_a=_SCREAMING_SNAKE_CASE		, already_has_special_tokens=_SCREAMING_SNAKE_CASE		)

			if token_ids_a is not None:
					return [1] + ([0] * len(_SCREAMING_SNAKE_CASE		)) + [1] + ([0] * len(_SCREAMING_SNAKE_CASE		)) + [1]
			return [1] + ([0] * len(_SCREAMING_SNAKE_CASE		)) + [1]




	def 							UpperCAmelCase__( self						:		Dict		, _SCREAMING_SNAKE_CASE						:		List[int]		, _SCREAMING_SNAKE_CASE						:		Optional[List[int]] = None		)->	List[int]:
			lowerCAmelCase__       :      int   					= [self.sep_token_id]
			lowerCAmelCase__       :      List[str]   					= [self.cls_token_id]

			if token_ids_a is None:
					return len(cls + token_ids_a + sep		) * [0]
			return len(cls + token_ids_a + sep		) * [0] + len(token_ids_a + sep		) * [1]




	def 							UpperCAmelCase__( self						:		Any		, _SCREAMING_SNAKE_CASE						:		str		, _SCREAMING_SNAKE_CASE						:		Optional[str] = None		)->	Tuple[str]:





			if not os.path.isdir(_SCREAMING_SNAKE_CASE		):
					logger.error(F'Vocabulary path ({save_directory}) should be a directory'		)
					return
			lowerCAmelCase__       :      Optional[int]   					= os.path.join(
			    _SCREAMING_SNAKE_CASE		, (filename_prefix + '''-''' if filename_prefix else '''''') + VOCAB_FILES_NAMES['''vocab_file''']		)

			if os.path.abspath(self.vocab_file		) != os.path.abspath(_SCREAMING_SNAKE_CASE		) and os.path.isfile(self.vocab_file		):
					copyfile(self.vocab_file		, _SCREAMING_SNAKE_CASE		)
			elif not os.path.isfile(self.vocab_file		):
					with open(_SCREAMING_SNAKE_CASE		, '''wb'''		) as fi:
							lowerCAmelCase__       :      Union[str, Any]   					= self.sp_model.serialized_model_proto()
							fi.write(_SCREAMING_SNAKE_CASE		)

			return (out_vocab_file,)








class  _a							:




	def __init__( self						:		str		, _SCREAMING_SNAKE_CASE						:		str		, _SCREAMING_SNAKE_CASE						:		Optional[int]		, _SCREAMING_SNAKE_CASE						:		List[Any]		)->	Tuple:
			lowerCAmelCase__       :      List[Any]   					= None
			lowerCAmelCase__       :      int   					= None
			lowerCAmelCase__       :      Union[str, Any]   					= graph

			self._normalize_graph(_SCREAMING_SNAKE_CASE		, _SCREAMING_SNAKE_CASE		)
			lowerCAmelCase__       :      Tuple   					= len(_SCREAMING_SNAKE_CASE		)
			lowerCAmelCase__       :      Optional[int]   					= None




	def 							UpperCAmelCase__( self						:		Union[str, Any]		, _SCREAMING_SNAKE_CASE						:		Optional[Any]		, _SCREAMING_SNAKE_CASE						:		Union[str, Any]		)->	Union[str, Any]:
			if sources is int:
					lowerCAmelCase__       :      List[Any]   					= [sources]
			if sinks is int:
					lowerCAmelCase__       :      Optional[Any]   					= [sinks]

			if len(_SCREAMING_SNAKE_CASE		) == 0 or len(_SCREAMING_SNAKE_CASE		) == 0:
					return

			lowerCAmelCase__       :      Union[str, Any]   					= sources[0]
			lowerCAmelCase__       :      Dict   					= sinks[0]

			# make fake vertex if there are more
			# than one source or sink
			if len(_SCREAMING_SNAKE_CASE		) > 1 or len(_SCREAMING_SNAKE_CASE		) > 1:
					lowerCAmelCase__       :      List[Any]   					= 0
					for i in sources:
							max_input_flow += sum(self.graph[i]		)

					lowerCAmelCase__       :      Any   					= len(self.graph		) + 1
					for room in self.graph:
							room.insert(0		, 0		)
					self.graph.insert(0		, [0] * size		)
					for i in sources:
							lowerCAmelCase__       :      Optional[Any]   					= max_input_flow
					lowerCAmelCase__       :      List[str]   					= 0

					lowerCAmelCase__       :      List[Any]   					= len(self.graph		) + 1
					for room in self.graph:
							room.append(0		)
					self.graph.append([0] * size		)
					for i in sinks:
							lowerCAmelCase__       :      str   					= max_input_flow
					lowerCAmelCase__       :      Tuple   					= size - 1




	def 							UpperCAmelCase__( self						:		Union[str, Any]		)->	Union[str, Any]:
			if self.maximum_flow_algorithm is None:
					raise Exception('''You need to set maximum flow algorithm before.'''		)
			if self.source_index is None or self.sink_index is None:
					return 0

			self.maximum_flow_algorithm.execute()
			return self.maximum_flow_algorithm.getMaximumFlow()




	def 							UpperCAmelCase__( self						:		str		, _SCREAMING_SNAKE_CASE						:		List[Any]		)->	int:
			lowerCAmelCase__       :      int   					= algorithm(self		)





class  _a							:




	def __init__( self						:		Optional[Any]		, _SCREAMING_SNAKE_CASE						:		Tuple		)->	Union[str, Any]:
			lowerCAmelCase__       :      Tuple   					= flow_network
			lowerCAmelCase__       :      Dict   					= flow_network.verticesCount
			lowerCAmelCase__       :      Optional[Any]   					= flow_network.sourceIndex
			lowerCAmelCase__       :      Optional[Any]   					= flow_network.sinkIndex
			# it's just a reference, so you shouldn't change
			# it in your algorithms, use deep copy before doing that
			lowerCAmelCase__       :      str   					= flow_network.graph
			lowerCAmelCase__       :      Optional[int]   					= False




	def 							UpperCAmelCase__( self						:		List[str]		)->	Dict:
			if not self.executed:
					self._algorithm()
					lowerCAmelCase__       :      Any   					= True




	def 							UpperCAmelCase__( self						:		Optional[Any]		)->	int:
			pass





class  _a							(    _lowercase):




	def __init__( self						:		Any		, _SCREAMING_SNAKE_CASE						:		List[Any]		)->	Union[str, Any]:
			super().__init__(_SCREAMING_SNAKE_CASE		)
			# use this to save your result
			lowerCAmelCase__       :      Dict   					= -1




	def 							UpperCAmelCase__( self						:		Any		)->	Optional[Any]:
			if not self.executed:
					raise Exception('''You should execute algorithm before using its result!'''		)

			return self.maximum_flow





class  _a							(    _lowercase):




	def __init__( self						:		Any		, _SCREAMING_SNAKE_CASE						:		List[str]		)->	List[str]:
			super().__init__(_SCREAMING_SNAKE_CASE		)

			lowerCAmelCase__       :      Any   					= [[0] * self.verticies_count for i in range(self.verticies_count		)]

			lowerCAmelCase__       :      Optional[Any]   					= [0] * self.verticies_count
			lowerCAmelCase__       :      str   					= [0] * self.verticies_count




	def 							UpperCAmelCase__( self						:		Any		)->	List[Any]:
			lowerCAmelCase__       :      Optional[Any]   					= self.verticies_count

			# push some substance to graph
			for nextvertex_index, bandwidth in enumerate(self.graph[self.source_index]		):
					self.preflow[self.source_index][nextvertex_index] += bandwidth
					self.preflow[nextvertex_index][self.source_index] -= bandwidth
					self.excesses[nextvertex_index] += bandwidth

			# Relabel-to-front selection rule
			lowerCAmelCase__       :      Any   					= [
			    i
			    for i in range(self.verticies_count		)
			    if i != self.source_index and i != self.sink_index
			]

			# move through list
			lowerCAmelCase__       :      str   					= 0
			while i < len(_SCREAMING_SNAKE_CASE		):
					lowerCAmelCase__       :      Union[str, Any]   					= vertices_list[i]
					lowerCAmelCase__       :      Any   					= self.heights[vertex_index]
					self.process_vertex(_SCREAMING_SNAKE_CASE		)
					if self.heights[vertex_index] > previous_height:
							# if it was relabeled, swap elements
							# and start from 0 index
							vertices_list.insert(0		, vertices_list.pop(_SCREAMING_SNAKE_CASE		)		)
							lowerCAmelCase__       :      Optional[Any]   					= 0
					else:
							i += 1

			lowerCAmelCase__       :      Optional[Any]   					= sum(self.preflow[self.source_index]		)




	def 							UpperCAmelCase__( self						:		List[str]		, _SCREAMING_SNAKE_CASE						:		Optional[Any]		)->	Optional[int]:
			while self.excesses[vertex_index] > 0:
					for neighbour_index in range(self.verticies_count		):
							# if it's neighbour and current vertex is higher
							if (
							    self.graph[vertex_index][neighbour_index]
							    - self.preflow[vertex_index][neighbour_index]
							    > 0
							    and self.heights[vertex_index] > self.heights[neighbour_index]
							):
									self.push(_SCREAMING_SNAKE_CASE		, _SCREAMING_SNAKE_CASE		)

					self.relabel(_SCREAMING_SNAKE_CASE		)




	def 							UpperCAmelCase__( self						:		int		, _SCREAMING_SNAKE_CASE						:		Optional[Any]		, _SCREAMING_SNAKE_CASE						:		Union[str, Any]		)->	Union[str, Any]:
			lowerCAmelCase__       :      Union[str, Any]   					= min(
			    self.excesses[from_index]		, self.graph[from_index][to_index] - self.preflow[from_index][to_index]		, )
			self.preflow[from_index][to_index] += preflow_delta
			self.preflow[to_index][from_index] -= preflow_delta
			self.excesses[from_index] -= preflow_delta
			self.excesses[to_index] += preflow_delta




	def 							UpperCAmelCase__( self						:		Optional[int]		, _SCREAMING_SNAKE_CASE						:		Any		)->	Optional[int]:
			lowerCAmelCase__       :      Optional[int]   					= None
			for to_index in range(self.verticies_count		):
					if (
					    self.graph[vertex_index][to_index]
					    - self.preflow[vertex_index][to_index]
					    > 0
					) and (min_height is None or self.heights[to_index] < min_height):
							lowerCAmelCase__       :      List[Any]   					= self.heights[to_index]

			if min_height is not None:
					lowerCAmelCase__       :      Optional[Any]   					= min_height + 1


if __name__ == "__main__":
		lowerCamelCase						=		[0]
		lowerCamelCase						=		[3]
		# graph = [
		#     [0, 0, 4, 6, 0, 0],
		#     [0, 0, 5, 2, 0, 0],
		#     [0, 0, 0, 0, 4, 4],
		#     [0, 0, 0, 0, 6, 6],
		#     [0, 0, 0, 0, 0, 0],
		#     [0, 0, 0, 0, 0, 0],
		# ]
		lowerCamelCase						=		[[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]]

		# prepare our network
		lowerCamelCase						=		FlowNetwork(graph, entrances, exits)
		# set algorithm
		flow_network.set_maximum_flow_algorithm(PushRelabelExecutor)
		# and calculate
		lowerCamelCase						=		flow_network.find_maximum_flow()

		print(f'''maximum flow is {maximum_flow}''')




