


'''simple docstring'''


from abc import ABC, abstractmethod
from typing import List, Optional





class     lowercase__  (						_snake_case					):





							'''simple docstring'''


							def __init__(    self  ):
											# test for the above condition
											self.test()






							def UpperCAmelCase_	(    self  ):
											_SCREAMING_SNAKE_CASE :       int     		=      0
											_SCREAMING_SNAKE_CASE :       Any     		=      False
											while not completed:
															if counter == 1:
																			self.reset()
															_SCREAMING_SNAKE_CASE :       int     		=      self.advance()
															if not self.does_advance(__snake_case  ):
																			raise Exception(
																			    """Custom Constraint is not defined correctly. self.does_advance(self.advance()) must be true."""  )

															_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       List[Any]     		=      self.update(__snake_case  )
															counter += 1

															if counter > 1_0000:
																			raise Exception("""update() does not fulfill the constraint."""  )

											if self.remaining() != 0:
															raise Exception("""Custom Constraint is not defined correctly."""  )






							@abstractmethod
							def UpperCAmelCase_	(    self  ):
											raise NotImplementedError(
											    f"""{self.__class__} is an abstract class. Only classes inheriting this class can be called."""  )






							@abstractmethod
							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											raise NotImplementedError(
											    f"""{self.__class__} is an abstract class. Only classes inheriting this class can be called."""  )






							@abstractmethod
							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											raise NotImplementedError(
											    f"""{self.__class__} is an abstract class. Only classes inheriting this class can be called."""  )






							@abstractmethod
							def UpperCAmelCase_	(    self  ):
											raise NotImplementedError(
											    f"""{self.__class__} is an abstract class. Only classes inheriting this class can be called."""  )






							@abstractmethod
							def UpperCAmelCase_	(    self  ):
											raise NotImplementedError(
											    f"""{self.__class__} is an abstract class. Only classes inheriting this class can be called."""  )






							@abstractmethod
							def UpperCAmelCase_	(    self    ,					__snake_case=False  ):
											raise NotImplementedError(
											    f"""{self.__class__} is an abstract class. Only classes inheriting this class can be called."""  )





class     lowercase__  (						_snake_case					):





							'''simple docstring'''


							def __init__(    self    ,					__snake_case  ):
											super(__snake_case    ,					self  ).__init__()

											if not isinstance(__snake_case    ,					__snake_case  ) or len(__snake_case  ) == 0:
															raise ValueError(f"""`token_ids` has to be a non-empty list, but is {token_ids}."""  )
											if any((not isinstance(__snake_case    ,					__snake_case  ) or token_id < 0) for token_id in token_ids  ):
															raise ValueError(f"""Each list in `token_ids` has to be a list of positive integers, but is {token_ids}."""  )

											_SCREAMING_SNAKE_CASE :       Optional[Any]     		=      token_ids

											_SCREAMING_SNAKE_CASE :       List[str]     		=      len(self.token_ids  )
											_SCREAMING_SNAKE_CASE :       Dict     		=      -1  # the index of the currently fulfilled step
											_SCREAMING_SNAKE_CASE :       Dict     		=      False






							def UpperCAmelCase_	(    self  ):
											if self.completed:
															return None
											return self.token_ids[self.fulfilled_idx + 1]






							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											if not isinstance(__snake_case    ,					__snake_case  ):
															raise ValueError(f"""`token_id` has to be an `int`, but is {token_id} of type {type(__snake_case  )}"""  )

											if self.completed:
															return False

											return token_id == self.token_ids[self.fulfilled_idx + 1]






							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											if not isinstance(__snake_case    ,					__snake_case  ):
															raise ValueError(f"""`token_id` has to be an `int`, but is {token_id} of type {type(__snake_case  )}"""  )

											_SCREAMING_SNAKE_CASE :       Tuple     		=      False
											_SCREAMING_SNAKE_CASE :       Tuple     		=      False
											_SCREAMING_SNAKE_CASE :       List[str]     		=      False

											if self.does_advance(__snake_case  ):
															self.fulfilled_idx += 1
															_SCREAMING_SNAKE_CASE :       Tuple     		=      True
															if self.fulfilled_idx == (self.seqlen - 1):
																			_SCREAMING_SNAKE_CASE :       Optional[int]     		=      True
															_SCREAMING_SNAKE_CASE :       Optional[int]     		=      completed
											else:
															# failed to make progress.
															_SCREAMING_SNAKE_CASE :       Dict     		=      True
															self.reset()
											return stepped, completed, reset






							def UpperCAmelCase_	(    self  ):
											_SCREAMING_SNAKE_CASE :       Optional[int]     		=      False
											_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      0






							def UpperCAmelCase_	(    self  ):
											return self.seqlen - (self.fulfilled_idx + 1)






							def UpperCAmelCase_	(    self    ,					__snake_case=False  ):
											_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      PhrasalConstraint(self.token_ids  )

											if stateful:
															_SCREAMING_SNAKE_CASE :       Any     		=      self.seqlen
															_SCREAMING_SNAKE_CASE :       Optional[Any]     		=      self.fulfilled_idx
															_SCREAMING_SNAKE_CASE :       str     		=      self.completed

											return new_constraint





class     lowercase__  :





							'''simple docstring'''


							def __init__(    self    ,					__snake_case    ,					__snake_case=True  ):
											_SCREAMING_SNAKE_CASE :       Tuple     		=      max([len(__snake_case  ) for one in nested_token_ids]  )

											_SCREAMING_SNAKE_CASE :       str     		=      {}
											for token_ids in nested_token_ids:
															_SCREAMING_SNAKE_CASE :       Dict     		=      root
															for tidx, token_id in enumerate(__snake_case  ):
																			if token_id not in level:
																							_SCREAMING_SNAKE_CASE :       Tuple     		=      {}

																			_SCREAMING_SNAKE_CASE :       Dict     		=      level[token_id]

											if no_subsets and self.has_subsets(__snake_case    ,					__snake_case  ):
															raise ValueError(
															    """Each list in `nested_token_ids` can't be a complete subset of another list, but is"""
															    f""" {nested_token_ids}."""  )

											_SCREAMING_SNAKE_CASE :       str     		=      root






							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											_SCREAMING_SNAKE_CASE :       Any     		=      self.trie

											for current_token in current_seq:
															_SCREAMING_SNAKE_CASE :       Optional[Any]     		=      start[current_token]

											_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      list(start.keys()  )

											return next_tokens






							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											_SCREAMING_SNAKE_CASE :       Optional[int]     		=      self.next_tokens(__snake_case  )

											return len(__snake_case  ) == 0






							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											_SCREAMING_SNAKE_CASE :       Tuple     		=      list(root.values()  )
											if len(__snake_case  ) == 0:
															return 1
											else:
															return sum([self.count_leaves(__snake_case  ) for nn in next_nodes]  )






							def UpperCAmelCase_	(    self    ,					__snake_case    ,					__snake_case  ):
											_SCREAMING_SNAKE_CASE :       List[str]     		=      self.count_leaves(__snake_case  )
											return len(__snake_case  ) != leaf_count





class     lowercase__  (						_snake_case					):





							'''simple docstring'''


							def __init__(    self    ,					__snake_case  ):
											super(__snake_case    ,					self  ).__init__()

											if not isinstance(__snake_case    ,					__snake_case  ) or len(__snake_case  ) == 0:
															raise ValueError(f"""`nested_token_ids` has to be a non-empty list, but is {nested_token_ids}."""  )
											if any(not isinstance(__snake_case    ,					__snake_case  ) for token_ids in nested_token_ids  ):
															raise ValueError(f"""`nested_token_ids` has to be a list of lists, but is {nested_token_ids}."""  )
											if any(
											    any((not isinstance(__snake_case    ,					__snake_case  ) or token_id < 0) for token_id in token_ids  )
											    for token_ids in nested_token_ids  ):
															raise ValueError(
															    f"""Each list in `nested_token_ids` has to be a list of positive integers, but is {nested_token_ids}."""  )

											_SCREAMING_SNAKE_CASE :       Any     		=      DisjunctiveTrie(__snake_case  )
											_SCREAMING_SNAKE_CASE :       int     		=      nested_token_ids

											_SCREAMING_SNAKE_CASE :       Tuple     		=      self.trie.max_height
											_SCREAMING_SNAKE_CASE :       List[str]     		=      []
											_SCREAMING_SNAKE_CASE :       List[Any]     		=      False






							def UpperCAmelCase_	(    self  ):
											_SCREAMING_SNAKE_CASE :       Optional[Any]     		=      self.trie.next_tokens(self.current_seq  )

											if len(__snake_case  ) == 0:
															return None
											else:
															return token_list






							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											if not isinstance(__snake_case    ,					__snake_case  ):
															raise ValueError(f"""`token_id` is supposed to be type `int`, but is {token_id} of type {type(__snake_case  )}"""  )

											_SCREAMING_SNAKE_CASE :       Any     		=      self.trie.next_tokens(self.current_seq  )

											return token_id in next_tokens






							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											if not isinstance(__snake_case    ,					__snake_case  ):
															raise ValueError(f"""`token_id` is supposed to be type `int`, but is {token_id} of type {type(__snake_case  )}"""  )

											_SCREAMING_SNAKE_CASE :       Optional[int]     		=      False
											_SCREAMING_SNAKE_CASE :       int     		=      False
											_SCREAMING_SNAKE_CASE :       Any     		=      False

											if self.does_advance(__snake_case  ):
															self.current_seq.append(__snake_case  )
															_SCREAMING_SNAKE_CASE :       Optional[Any]     		=      True
											else:
															_SCREAMING_SNAKE_CASE :       List[str]     		=      True
															self.reset()

											_SCREAMING_SNAKE_CASE :       List[Any]     		=      self.trie.reached_leaf(self.current_seq  )
											_SCREAMING_SNAKE_CASE :       List[Any]     		=      completed

											return stepped, completed, reset






							def UpperCAmelCase_	(    self  ):
											_SCREAMING_SNAKE_CASE :       Optional[Any]     		=      False
											_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      []






							def UpperCAmelCase_	(    self  ):
											if self.completed:
															# since this can be completed without reaching max height
															return 0
											else:
															return self.seqlen - len(self.current_seq  )






							def UpperCAmelCase_	(    self    ,					__snake_case=False  ):
											_SCREAMING_SNAKE_CASE :       int     		=      DisjunctiveConstraint(self.token_ids  )

											if stateful:
															_SCREAMING_SNAKE_CASE :       str     		=      self.seqlen
															_SCREAMING_SNAKE_CASE :       Dict     		=      self.current_seq
															_SCREAMING_SNAKE_CASE :       Dict     		=      self.completed

											return new_constraint





class     lowercase__  :





							'''simple docstring'''


							def __init__(    self    ,					__snake_case  ):
											_SCREAMING_SNAKE_CASE :       Optional[int]     		=      constraints

											# max # of steps required to fulfill a given constraint
											_SCREAMING_SNAKE_CASE :       Any     		=      max([c.seqlen for c in constraints]  )
											_SCREAMING_SNAKE_CASE :       Tuple     		=      len(__snake_case  )
											_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      False

											self.init_state()






							def UpperCAmelCase_	(    self  ):
											_SCREAMING_SNAKE_CASE :       Any     		=      []
											_SCREAMING_SNAKE_CASE :       Tuple     		=      None
											_SCREAMING_SNAKE_CASE :       Optional[int]     		=      [constraint.copy(stateful=__snake_case  ) for constraint in self.constraints]






							def UpperCAmelCase_	(    self  ):
											_SCREAMING_SNAKE_CASE :       Optional[Any]     		=      0
											if self.inprogress_constraint:
															# extra points for having a constraint mid-fulfilled
															add += self.max_seqlen - self.inprogress_constraint.remaining()

											return (len(self.complete_constraints  ) * self.max_seqlen) + add






							def UpperCAmelCase_	(    self  ):
											_SCREAMING_SNAKE_CASE :       Dict     		=      []
											if self.inprogress_constraint is None:
															for constraint in self.pending_constraints:  # "pending" == "unfulfilled yet"
																			_SCREAMING_SNAKE_CASE :       List[Any]     		=      constraint.advance()
																			if isinstance(__snake_case    ,					__snake_case  ):
																							token_list.append(__snake_case  )
																			elif isinstance(__snake_case    ,					__snake_case  ):
																							token_list.extend(__snake_case  )
											else:
															_SCREAMING_SNAKE_CASE :       int     		=      self.inprogress_constraint.advance()
															if isinstance(__snake_case    ,					__snake_case  ):
																			token_list.append(__snake_case  )
															elif isinstance(__snake_case    ,					__snake_case  ):
																			token_list.extend(__snake_case  )

											if len(__snake_case  ) == 0:
															return None
											else:
															return token_list






							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											self.init_state()

											if token_ids is not None:
															for token in token_ids:
																			# completes or steps **one** constraint
																			_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      self.add(__snake_case  )

																			# the entire list of constraints are fulfilled
																			if self.completed:
																							break






							def UpperCAmelCase_	(    self    ,					__snake_case  ):
											if not isinstance(__snake_case    ,					__snake_case  ):
															raise ValueError(f"""`token_id` should be an `int`, but is `{token_id}`."""  )

											_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       Any     		=      False, False

											if self.completed:
															_SCREAMING_SNAKE_CASE :       Dict     		=      True
															_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      False
															return complete, stepped

											if self.inprogress_constraint is not None:
															# In the middle of fulfilling a constraint. If the `token_id` *does* makes an incremental progress to current
															# job, simply update the state

															_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       List[str]     		=      self.inprogress_constraint.update(__snake_case  )
															if reset:
																			# 1. If the next token breaks the progress, then we must restart.
																			#     e.g. constraint = "I love pies" and sequence so far is "I love" but `token_id` == "books".

																			#     But that doesn't mean we self.init_state(), since we only reset the state for this particular
																			#     constraint, not the full list of constraints.

																			self.pending_constraints.append(self.inprogress_constraint.copy(stateful=__snake_case  )  )
																			_SCREAMING_SNAKE_CASE :       Any     		=      None

															if complete:
																			# 2. If the next token completes the constraint, move it to completed list, set
																			#     inprogress to None. If there are no pending constraints either, then this full list of constraints
																			#     is complete.

																			self.complete_constraints.append(self.inprogress_constraint  )
																			_SCREAMING_SNAKE_CASE :       Dict     		=      None

																			if len(self.pending_constraints  ) == 0:
																							# we're done!
																							_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      True

											else:
															# Not in the middle of fulfilling a constraint. So does this `token_id` helps us step towards any of our list
															# of constraints?

															for cidx, pending_constraint in enumerate(self.pending_constraints  ):
																			if pending_constraint.does_advance(__snake_case  ):
																							_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       Any     		=      pending_constraint.update(__snake_case  )

																							if not stepped:
																											raise Exception(
																											    """`constraint.update(token_id)` is not yielding incremental progress, """
																											    """even though `constraint.does_advance(token_id)` is true."""  )

																							if complete:
																											self.complete_constraints.append(__snake_case  )
																											_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      None

																							if not complete and stepped:
																											_SCREAMING_SNAKE_CASE :       str     		=      pending_constraint

																							if complete or stepped:
																											# If we made any progress at all, then it's at least not a "pending constraint".

																											_SCREAMING_SNAKE_CASE :       Tuple     		=      (
																											    self.pending_constraints[:cidx] + self.pending_constraints[cidx + 1 :]
																											)

																											if len(self.pending_constraints  ) == 0 and self.inprogress_constraint is None:
																															# If there's no longer any pending after this and no inprogress either, then we must be
																															# complete.

																															_SCREAMING_SNAKE_CASE :       int     		=      True

																											break  # prevent accidentally stepping through multiple constraints with just one token.

											return complete, stepped






							def UpperCAmelCase_	(    self    ,					__snake_case=True  ):
											_SCREAMING_SNAKE_CASE :       List[str]     		=      ConstraintListState(self.constraints  )  # we actually never though self.constraints objects
											# throughout this process. So it's at initialization state.

											if stateful:
															_SCREAMING_SNAKE_CASE :       List[str]     		=      [
															    constraint.copy(stateful=__snake_case  ) for constraint in self.complete_constraints
															]
															if self.inprogress_constraint is not None:
																			_SCREAMING_SNAKE_CASE :       List[Any]     		=      self.inprogress_constraint.copy(stateful=__snake_case  )
															_SCREAMING_SNAKE_CASE :       Tuple     		=      [constraint.copy() for constraint in self.pending_constraints]

											return new_state








'''simple docstring'''


def 			snake_case_   (  SCREAMING_SNAKE_CASE__     ):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE :       str     		=      0
				for ch in input_str:
								_SCREAMING_SNAKE_CASE :       Optional[Any]     		=      ord(SCREAMING_SNAKE_CASE__     )
								_SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      pow(2							,      SCREAMING_SNAKE_CASE__     )

								# If we already turned on bit for current character's unicode
								if bitmap >> ch_unicode & 1 == 1:
												return False
								bitmap |= ch_bit_index_on
				return True


if __name__ == "__main__":
				import doctest

				doctest.testmod()




