'''simple docstring'''






from collections import deque




class    a :



  """simple docstring"""







  def __init__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Dict		= process_name  # process name
    __UpperCAmelCase:					Optional[int]		= arrival_time  # arrival time of the process
    # completion time of finished process or last interrupted time
    __UpperCAmelCase:					Tuple		= arrival_time
    __UpperCAmelCase:					List[str]		= burst_time  # remaining burst time
    __UpperCAmelCase:					List[str]		= 0  # total time of the process wait in ready queue
    __UpperCAmelCase:					Union[str, Any]		= 0  # time from arrival time to completion time




class    a :



  """simple docstring"""







  def __init__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_   ,    snake_case_   ,    ):

    '''simple docstring'''







    __UpperCAmelCase:					str		= number_of_queues
    # time slice of queues that round robin algorithm applied
    __UpperCAmelCase:					Union[str, Any]		= time_slices
    # unfinished process is in this ready_queue
    __UpperCAmelCase:					Dict		= queue
    # current time
    __UpperCAmelCase:					int		= current_time
    # finished process is in this sequence queue
    __UpperCAmelCase:					deque[Process]		= deque()







  def    lowercase_  (							self					):

    '''simple docstring'''







    __UpperCAmelCase:					str		= []
    for i in range(len(self.finish_queue					)					):
      sequence.append(self.finish_queue[i].process_name					)
    return sequence







  def    lowercase_  (							self   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					List[Any]		= []
    for i in range(len(snake_case_					)					):
      waiting_times.append(queue[i].waiting_time					)
    return waiting_times







  def    lowercase_  (							self   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					str		= []
    for i in range(len(snake_case_					)					):
      turnaround_times.append(queue[i].turnaround_time					)
    return turnaround_times







  def    lowercase_  (							self   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Optional[int]		= []
    for i in range(len(snake_case_					)					):
      completion_times.append(queue[i].stop_time					)
    return completion_times







  def    lowercase_  (							self   ,    snake_case_					):

    '''simple docstring'''







    return [q.burst_time for q in queue]







  def    lowercase_  (							self   ,    snake_case_					):

    '''simple docstring'''







    process.waiting_time += self.current_time - process.stop_time
    return process.waiting_time







  def    lowercase_  (							self   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					deque[Process]		= deque()  # sequence deque of finished process
    while len(snake_case_					) != 0:
      __UpperCAmelCase:					Optional[int]		= ready_queue.popleft()  # current process

      # if process's arrival time is later than current time, update current time
      if self.current_time < cp.arrival_time:
        self.current_time += cp.arrival_time

      # update waiting time of current process
      self.update_waiting_time(snake_case_					)
      # update current time
      self.current_time += cp.burst_time
      # finish the process and set the process's burst-time 0
      __UpperCAmelCase:					Any		= 0
      # set the process's turnaround time because it is finished
      __UpperCAmelCase:					Tuple		= self.current_time - cp.arrival_time
      # set the completion time
      __UpperCAmelCase:					Optional[Any]		= self.current_time
      # add the process to queue that has finished queue
      finished.append(snake_case_					)

    self.finish_queue.extend(snake_case_					)  # add finished process to finish queue
    # FCFS will finish all remaining processes
    return finished







  def    lowercase_  (							self   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					deque[Process]		= deque()  # sequence deque of terminated process
    # just for 1 cycle and unfinished processes will go back to queue
    for _ in range(len(snake_case_					)					):
      __UpperCAmelCase:					Optional[int]		= ready_queue.popleft()  # current process

      # if process's arrival time is later than current time, update current time
      if self.current_time < cp.arrival_time:
        self.current_time += cp.arrival_time

      # update waiting time of unfinished processes
      self.update_waiting_time(snake_case_					)
      # if the burst time of process is bigger than time-slice
      if cp.burst_time > time_slice:
        # use CPU for only time-slice
        self.current_time += time_slice
        # update remaining burst time
        cp.burst_time -= time_slice
        # update end point time
        __UpperCAmelCase:					Dict		= self.current_time
        # locate the process behind the queue because it is not finished
        ready_queue.append(snake_case_					)
      else:
        # use CPU for remaining burst time
        self.current_time += cp.burst_time
        # set burst time 0 because the process is finished
        __UpperCAmelCase:					Union[str, Any]		= 0
        # set the finish time
        __UpperCAmelCase:					Optional[Any]		= self.current_time
        # update the process' turnaround time because it is finished
        __UpperCAmelCase:					List[str]		= self.current_time - cp.arrival_time
        # add the process to queue that has finished queue
        finished.append(snake_case_					)

    self.finish_queue.extend(snake_case_					)  # add finished process to finish queue
    # return finished processes queue and remaining processes queue
    return finished, ready_queue







  def    lowercase_  (							self					):

    '''simple docstring'''







    for i in range(self.number_of_queues - 1					):
      __UpperCAmelCase, __UpperCAmelCase:					List[Any]		= self.round_robin(
          self.ready_queue   ,    self.time_slices[i]					)
    #  the last queue has first_come_first_served algorithm
    self.first_come_first_served(self.ready_queue					)

    return self.finish_queue


if __name__ == "__main__":
    import doctest

    SCREAMING_SNAKE_CASE_	   =			Process('P1', 0, 53)
    SCREAMING_SNAKE_CASE_	   =			Process('P2', 0, 17)
    SCREAMING_SNAKE_CASE_	   =			Process('P3', 0, 68)
    SCREAMING_SNAKE_CASE_	   =			Process('P4', 0, 24)
    SCREAMING_SNAKE_CASE_	   =			3
    SCREAMING_SNAKE_CASE_	   =			[17, 25]
    SCREAMING_SNAKE_CASE_	   =			deque([Pa, Pa, Pa, Pa])

    if len(time_slices) != number_of_queues - 1:
        raise SystemExit(0)

    doctest.testmod(extraglobs={'queue': deque([Pa, Pa, Pa, Pa])})

    SCREAMING_SNAKE_CASE_	   =			Process('P1', 0, 53)
    SCREAMING_SNAKE_CASE_	   =			Process('P2', 0, 17)
    SCREAMING_SNAKE_CASE_	   =			Process('P3', 0, 68)
    SCREAMING_SNAKE_CASE_	   =			Process('P4', 0, 24)
    SCREAMING_SNAKE_CASE_	   =			3
    SCREAMING_SNAKE_CASE_	   =			[17, 25]
    SCREAMING_SNAKE_CASE_	   =			deque([Pa, Pa, Pa, Pa])
    SCREAMING_SNAKE_CASE_	   =			MLFQ(number_of_queues, time_slices, queue, 0)
    SCREAMING_SNAKE_CASE_	   =			mlfq.multi_level_feedback_queue()

    # print total waiting times of processes(P1, P2, P3, P4)
    print(
        F"""waiting time:\
        \t\t\t{MLFQ.calculate_waiting_time(mlfq, [Pa, Pa, Pa, Pa])}"""
    )
    # print completion times of processes(P1, P2, P3, P4)
    print(
        F"""completion time:\
        \t\t{MLFQ.calculate_completion_time(mlfq, [Pa, Pa, Pa, Pa])}"""
    )
    # print total turnaround times of processes(P1, P2, P3, P4)
    print(
        F"""turnaround time:\
        \t\t{MLFQ.calculate_turnaround_time(mlfq, [Pa, Pa, Pa, Pa])}"""
    )
    # print sequence of finished processes
    print(
        F"""sequence of finished processes:\
        {mlfq.calculate_sequence_of_finish_queue()}"""
    )
'''simple docstring'''






import inspect

import jax
import jax.lax as lax
import jax.numpy as jnp

from ..utils import add_start_docstrings
from ..utils.logging import get_logger


SCREAMING_SNAKE_CASE_	   =			get_logger(__name__)


SCREAMING_SNAKE_CASE_	   =			R'\n    Args:\n        input_ids (`jnp.ndarray` of shape `(batch_size, sequence_length)`):\n            Indices of input sequence tokens in the vocabulary.\n\n            Indices can be obtained using [`PreTrainedTokenizer`]. See [`PreTrainedTokenizer.encode`] and\n            [`PreTrainedTokenizer.__call__`] for details.\n\n            [What are input IDs?](../glossary#input-ids)\n        scores (`jnp.ndarray` of shape `(batch_size, config.vocab_size)`):\n            Prediction scores of a language modeling head. These can be logits for each vocabulary when not using beam\n            search or log softmax for each vocabulary token when using beam search\n        kwargs (`Dict[str, Any]`, *optional*):\n            Additional logits processor specific kwargs.\n\n    Return:\n        `jnp.ndarray` of shape `(batch_size, config.vocab_size)`: The processed prediction scores.\n\n'




class    a :



  """simple docstring"""







  @add_start_docstrings(snake_case_					)
  def __call__(							self   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    raise NotImplementedError(
        F'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''					)




class    a :



  """simple docstring"""







  @add_start_docstrings(snake_case_					)
  def __call__(							self   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    raise NotImplementedError(
        F'''{self.__class__} is an abstract class. Only classes inheriting this class can be called.'''					)




class    a (       __lowerCAmelCase				):



  """simple docstring"""







  @add_start_docstrings(snake_case_					)
  def __call__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_   ,    **snake_case_					):

    '''simple docstring'''







    for processor in self:
      __UpperCAmelCase:					str		= inspect.signature(processor.__call__					).parameters
      if len(snake_case_					) > 3:
        if not all(arg in kwargs for arg in list(function_args.keys()					)[2:]					):
          raise ValueError(
              F'''Make sure that all the required parameters: {list(function_args.keys()					)} for '''
              F'''{processor.__class__} are passed to the logits processor.'''					)
        __UpperCAmelCase:					List[Any]		= processor(snake_case_   ,    snake_case_   ,    snake_case_   ,    **snake_case_					)
      else:
        __UpperCAmelCase:					Optional[Any]		= processor(snake_case_   ,    snake_case_   ,    snake_case_					)
    return scores




class    a (       __lowerCAmelCase				):



  """simple docstring"""







  def __init__(							self   ,    snake_case_					):

    '''simple docstring'''







    if not isinstance(snake_case_   ,    snake_case_					) or not (temperature > 0):
      raise ValueError(F'''`temperature` has to be a strictly positive float, but is {temperature}'''					)

    __UpperCAmelCase:					Any		= temperature







  def __call__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Tuple		= scores / self.temperature
    return scores




class    a (       __lowerCAmelCase				):



  """simple docstring"""







  def __init__(							self   ,    snake_case_   ,    snake_case_ = -float("""Inf"""					)   ,    snake_case_ = 1					):

    '''simple docstring'''







    if not isinstance(snake_case_   ,    snake_case_					) or (top_p < 0 or top_p > 1.0):
      raise ValueError(F'''`top_p` has to be a float > 0 and < 1, but is {top_p}'''					)
    if not isinstance(snake_case_   ,    snake_case_					) or (min_tokens_to_keep < 1):
      raise ValueError(F'''`min_tokens_to_keep` has to be a positive integer, but is {min_tokens_to_keep}'''					)

    __UpperCAmelCase:					int		= top_p
    __UpperCAmelCase:					str		= filter_value
    __UpperCAmelCase:					List[Any]		= min_tokens_to_keep







  def __call__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase, __UpperCAmelCase:					List[Any]		= lax.top_k(snake_case_   ,    scores.shape[-1]					)

    __UpperCAmelCase:					Tuple		= jnp.full_like(snake_case_   ,    self.filter_value					)
    __UpperCAmelCase:					Optional[int]		= jax.nn.softmax(snake_case_   ,    axis=-1					).cumsum(axis=-1					)
    __UpperCAmelCase:					List[str]		= cumulative_probs < self.top_p

    # include the token that is higher than top_p as well
    __UpperCAmelCase:					str		= jnp.roll(snake_case_   ,    1					)
    score_mask |= score_mask.at[:, 0].set(snake_case_					)

    # min tokens to keep
    __UpperCAmelCase:					str		= score_mask.at[:, : self.min_tokens_to_keep].set(snake_case_					)

    __UpperCAmelCase:					List[Any]		= jnp.where(snake_case_   ,    snake_case_   ,    snake_case_					)
    __UpperCAmelCase:					Optional[Any]		= jax.lax.sort_key_val(snake_case_   ,    snake_case_					)[-1]

    return next_scores




class    a (       __lowerCAmelCase				):



  """simple docstring"""







  def __init__(							self   ,    snake_case_   ,    snake_case_ = -float("""Inf"""					)   ,    snake_case_ = 1					):

    '''simple docstring'''







    if not isinstance(snake_case_   ,    snake_case_					) or top_k <= 0:
      raise ValueError(F'''`top_k` has to be a strictly positive integer, but is {top_k}'''					)

    __UpperCAmelCase:					Optional[Any]		= max(snake_case_   ,    snake_case_					)
    __UpperCAmelCase:					List[str]		= filter_value







  def __call__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase, __UpperCAmelCase:					List[Any]		= scores.shape
    __UpperCAmelCase:					List[Any]		= jnp.full(batch_size * vocab_size   ,    self.filter_value					)

    __UpperCAmelCase:					Any		= min(self.top_k   ,    scores.shape[-1]					)  # Safety check
    __UpperCAmelCase, __UpperCAmelCase:					List[Any]		= lax.top_k(snake_case_   ,    snake_case_					)
    __UpperCAmelCase:					Optional[Any]		= jnp.broadcast_to((jnp.arange(snake_case_					) * vocab_size)[:, None]   ,    (batch_size, topk)					).flatten()
    __UpperCAmelCase:					List[Any]		= topk_scores.flatten()
    __UpperCAmelCase:					str		= topk_indices.flatten() + shift

    __UpperCAmelCase:					List[Any]		= next_scores_flat.at[topk_indices_flat].set(snake_case_					)
    __UpperCAmelCase:					Any		= next_scores_flat.reshape(snake_case_   ,    snake_case_					)
    return next_scores




class    a (       __lowerCAmelCase				):



  """simple docstring"""







  def __init__(							self   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					List[Any]		= bos_token_id







  def __call__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					List[Any]		= jnp.full(scores.shape   ,    -float("""inf"""					)					)

    __UpperCAmelCase:					Optional[Any]		= 1 - jnp.bool_(cur_len - 1					)

    __UpperCAmelCase:					Any		= jnp.where(snake_case_   ,    new_scores.at[:, self.bos_token_id].set(0					)   ,    snake_case_					)

    return scores




class    a (       __lowerCAmelCase				):



  """simple docstring"""







  def __init__(							self   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Union[str, Any]		= max_length
    __UpperCAmelCase:					List[str]		= eos_token_id







  def __call__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Optional[int]		= jnp.full(scores.shape   ,    -float("""inf"""					)					)

    __UpperCAmelCase:					List[str]		= 1 - jnp.bool_(cur_len - self.max_length + 1					)

    __UpperCAmelCase:					Any		= jnp.where(snake_case_   ,    new_scores.at[:, self.eos_token_id].set(0					)   ,    snake_case_					)

    return scores




class    a (       __lowerCAmelCase				):



  """simple docstring"""







  def __init__(							self   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    if not isinstance(snake_case_   ,    snake_case_					) or min_length < 0:
      raise ValueError(F'''`min_length` has to be a positive integer, but is {min_length}'''					)

    if not isinstance(snake_case_   ,    snake_case_					) or eos_token_id < 0:
      raise ValueError(F'''`eos_token_id` has to be a positive integer, but is {eos_token_id}'''					)

    __UpperCAmelCase:					List[Any]		= min_length
    __UpperCAmelCase:					Optional[int]		= eos_token_id







  def __call__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Union[str, Any]		= 1 - jnp.clip(cur_len - self.min_length   ,    0   ,    1					)

    __UpperCAmelCase:					int		= jnp.where(snake_case_   ,    scores.at[:, self.eos_token_id].set(-float("""inf"""					)					)   ,    snake_case_					)

    return scores




class    a (       __lowerCAmelCase				):



  """simple docstring"""







  def __init__(							self   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Any		= list(snake_case_					)
    __UpperCAmelCase:					Optional[Any]		= begin_index







  def __call__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Union[str, Any]		= 1 - jnp.bool_(cur_len - self.begin_index					)

    __UpperCAmelCase:					str		= jnp.where(snake_case_   ,    scores.at[:, self.begin_suppress_tokens].set(-float("""inf"""					)					)   ,    snake_case_					)

    return scores




class    a (       __lowerCAmelCase				):



  """simple docstring"""







  def __init__(							self   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Optional[Any]		= list(snake_case_					)







  def __call__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					int		= scores.at[..., self.suppress_tokens].set(-float("""inf"""					)					)

    return scores




class    a (       __lowerCAmelCase				):



  """simple docstring"""







  def __init__(							self   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Optional[int]		= dict(snake_case_					)
    # Converts the dictionary of format {index: token} containing the tokens to be forced to an array, where the
    # index of the array corresponds to the index of the token to be forced, for XLA compatibility.
    # Indexes without forced tokens will have a negative value.
    __UpperCAmelCase:					Optional[Any]		= jnp.ones((max(force_token_map.keys()					) + 1)   ,    dtype=jnp.intaa					) * -1
    for index, token in force_token_map.items():
      if token is not None:
        __UpperCAmelCase:					Union[str, Any]		= force_token_array.at[index].set(snake_case_					)
    __UpperCAmelCase:					Union[str, Any]		= jnp.intaa(snake_case_					)







  def __call__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    def _force_token(snake_case_					):
      __UpperCAmelCase:					List[Any]		= scores.shape[0]
      __UpperCAmelCase:					int		= self.force_token_array[generation_idx]

      __UpperCAmelCase:					Union[str, Any]		= jnp.ones_like(snake_case_   ,    dtype=scores.dtype					) * -float("""inf"""					)
      __UpperCAmelCase:					List[Any]		= jnp.zeros((batch_size, 1)   ,    dtype=scores.dtype					)
      __UpperCAmelCase:					List[Any]		= lax.dynamic_update_slice(snake_case_   ,    snake_case_   ,    (0, current_token)					)
      return new_scores

    __UpperCAmelCase:					Optional[int]		= lax.cond(
        cur_len >= self.force_token_array.shape[0]   ,    lambda: scores   ,    lambda: lax.cond(
            self.force_token_array[cur_len] >= 0   ,    lambda: _force_token(snake_case_					)   ,    lambda: scores   ,    )   ,    )
    return scores




class    a (       __lowerCAmelCase				):



  """simple docstring"""







  def __init__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					int		= generate_config.eos_token_id
    __UpperCAmelCase:					Union[str, Any]		= generate_config.no_timestamps_token_id
    __UpperCAmelCase:					Tuple		= generate_config.no_timestamps_token_id + 1

    __UpperCAmelCase:					Any		= decoder_input_length + 1

    if generate_config.is_multilingual:
      # room for language token and task token
      self.begin_index += 2
    if hasattr(snake_case_   ,    """max_initial_timestamp_index"""					):
      __UpperCAmelCase:					Optional[int]		= generate_config.max_initial_timestamp_index
    else:
      __UpperCAmelCase:					List[str]		= model_config.vocab_size
    if self.max_initial_timestamp_index is None:
      __UpperCAmelCase:					Any		= model_config.vocab_size







  def __call__(							self   ,    snake_case_   ,    snake_case_   ,    snake_case_					):

    '''simple docstring'''







    __UpperCAmelCase:					Any		= scores.at[:, self.no_timestamps_token_id].set(-float("""inf"""					)					)

    def handle_pairs(snake_case_   ,    snake_case_					):
      __UpperCAmelCase:					Optional[int]		= jnp.where((cur_len - self.begin_index) >= 1   ,    snake_case_   ,    snake_case_					)
      __UpperCAmelCase:					Union[str, Any]		= jnp.where(
          input_ids_k[cur_len - 1] >= self.timestamp_begin   ,    True and last_was_timestamp   ,    snake_case_   ,    )

      __UpperCAmelCase:					Union[str, Any]		= jnp.where((cur_len - self.begin_index) < 2   ,    snake_case_   ,    snake_case_					)
      __UpperCAmelCase:					List[str]		= jnp.where(
          input_ids_k[cur_len - 2] >= self.timestamp_begin   ,    snake_case_   ,    snake_case_   ,    )

      return jnp.where(
          snake_case_   ,    jnp.where(
              penultimate_was_timestamp > 0   ,    scores_k.at[self.timestamp_begin :].set(-float("""inf"""					)					)   ,    scores_k.at[: self.eos_token_id].set(-float("""inf"""					)					)   ,    )   ,    snake_case_   ,    )

    __UpperCAmelCase:					Dict		= jax.vmap(snake_case_					)(snake_case_   ,    snake_case_					)

    __UpperCAmelCase:					Dict		= jnp.where(cur_len == self.begin_index   ,    snake_case_   ,    snake_case_					)
    __UpperCAmelCase:					List[Any]		= jnp.where(
        self.max_initial_timestamp_index is not None   ,    True and apply_max_initial_timestamp   ,    snake_case_   ,    )

    __UpperCAmelCase:					List[str]		= self.timestamp_begin + self.max_initial_timestamp_index

    __UpperCAmelCase:					List[str]		= jnp.where(
        snake_case_   ,    scores.at[:, last_allowed + 1 :].set(-float("""inf"""					)					)   ,    snake_case_   ,    )

    # if sum of probability over timestamps is above any other token, sample timestamp
    __UpperCAmelCase:					Union[str, Any]		= jax.nn.log_softmax(snake_case_   ,    axis=-1					)

    def handle_cumulative_probs(snake_case_   ,    snake_case_					):
      __UpperCAmelCase:					int		= jax.nn.logsumexp(logprobs_k[self.timestamp_begin :]   ,    axis=-1					)
      __UpperCAmelCase:					Tuple		= jnp.max(logprobs_k[: self.timestamp_begin]					)
      return jnp.where(
          timestamp_logprob > max_text_token_logprob   ,    scores_k.at[: self.timestamp_begin].set(-float("""inf"""					)					)   ,    snake_case_   ,    )

    __UpperCAmelCase:					Tuple		= jax.vmap(snake_case_					)(snake_case_   ,    snake_case_					)

    return scores