



from collections import deque


class   snake_case_ :




       """simple docstring"""






       def __init__(     self     ,lowercase     ,lowercase     ,lowercase):

             """simple docstring"""





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


class   snake_case_ :




       """simple docstring"""






       def __init__(     self     ,lowercase     ,lowercase     ,lowercase     ,lowercase     ,):

             """simple docstring"""





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



       def  A_   (     self):

             """simple docstring"""





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



       def  A_   (     self     ,lowercase):

             """simple docstring"""





             UpperCAmelCase_  :	Dict				      =		[]
             for i in range(len(lowercase)):
                   waiting_times.append(queue[i].waiting_time)
             return waiting_times



       def  A_   (     self     ,lowercase):

             """simple docstring"""





             UpperCAmelCase_  :	List[Any]				      =		[]
             for i in range(len(lowercase)):
                   turnaround_times.append(queue[i].turnaround_time)
             return turnaround_times



       def  A_   (     self     ,lowercase):

             """simple docstring"""





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



       def  A_   (     self     ,lowercase):

             """simple docstring"""





             return [q.burst_time for q in queue]



       def  A_   (     self     ,lowercase):

             """simple docstring"""





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



       def  A_   (     self     ,lowercase):

             """simple docstring"""





             UpperCAmelCase_  :	deque[Process]				      =		deque()  # sequence deque of finished process
             while len(lowercase) != 0:
                   UpperCAmelCase_  :	Tuple				      =		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(lowercase)
                   # update current time
                   self.current_time += cp.burst_time
                   # finish the process and set the process's burst-time 0
                   UpperCAmelCase_  :	Optional[int]				      =		0
                   # set the process's turnaround time because it is finished
                   UpperCAmelCase_  :	Union[str, Any]				      =		self.current_time - cp.arrival_time
                   # set the completion time
                   UpperCAmelCase_  :	List[str]				      =		self.current_time
                   # add the process to queue that has finished queue
                   finished.append(lowercase)

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



       def  A_   (     self     ,lowercase     ,lowercase):

             """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(lowercase)):
                   UpperCAmelCase_  :	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(lowercase)
                   # 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_  :	List[str]				      =		self.current_time
                         # locate the process behind the queue because it is not finished
                         ready_queue.append(lowercase)
                   else:
                         # use CPU for remaining burst time
                         self.current_time += cp.burst_time
                         # set burst time 0 because the process is finished
                         UpperCAmelCase_  :	Dict				      =		0
                         # set the finish time
                         UpperCAmelCase_  :	Optional[int]				      =		self.current_time
                         # update the process' turnaround time because it is finished
                         UpperCAmelCase_  :	Dict				      =		self.current_time - cp.arrival_time
                         # add the process to queue that has finished queue
                         finished.append(lowercase)

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



       def  A_   (     self):

             """simple docstring"""





             for i in range(self.number_of_queues - 1):
                   UpperCAmelCase_      ,      UpperCAmelCase_  :	List[str]				      =		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

   __lowerCamelCase         =			Process('''P1''', 0, 53)
   __lowerCamelCase         =			Process('''P2''', 0, 17)
   __lowerCamelCase         =			Process('''P3''', 0, 68)
   __lowerCamelCase         =			Process('''P4''', 0, 24)
   __lowerCamelCase         =			3
   __lowerCamelCase         =			[17, 25]
   __lowerCamelCase         =			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])})

   __lowerCamelCase         =			Process('''P1''', 0, 53)
   __lowerCamelCase         =			Process('''P2''', 0, 17)
   __lowerCamelCase         =			Process('''P3''', 0, 68)
   __lowerCamelCase         =			Process('''P4''', 0, 24)
   __lowerCamelCase         =			3
   __lowerCamelCase         =			[17, 25]
   __lowerCamelCase         =			deque([Pa, Pa, Pa, Pa])
   __lowerCamelCase         =			MLFQ(number_of_queues, time_slices, queue, 0)
   __lowerCamelCase         =			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()}'''
   )





import operator







def    _snake_case (       __snake_case					,  __snake_case = False					,  __snake_case = None    )     ->     list:






      '''simple docstring'''







      UpperCAmelCase_  :	Optional[int]				      =		operator.lt if reverse else operator.gt
      UpperCAmelCase_  :	int				      =		solution or []

      if not arr:
            return solution

      UpperCAmelCase_  :	Union[str, Any]				      =		[arr.pop(0    )]
      for i, item in enumerate(__snake_case    ):
            if _operator(__snake_case					,  sublist[-1]    ):
                  sublist.append(__snake_case    )
                  arr.pop(__snake_case    )

    #  merging sublist into solution list
      if not solution:
            solution.extend(__snake_case    )
      else:
            while sublist:
                  UpperCAmelCase_  :	Optional[int]				      =		sublist.pop(0    )
                  for i, xx in enumerate(__snake_case    ):
                        if not _operator(__snake_case					,  __snake_case    ):
                              solution.insert(__snake_case					,  __snake_case    )
                              break
                  else:
                        solution.append(__snake_case    )

      strand_sort(__snake_case					,  __snake_case					,  __snake_case    )
      return solution


if __name__ == "__main__":
   assert strand_sort([4, 3, 5, 1, 2]) == [1, 2, 3, 4, 5]
   assert strand_sort([4, 3, 5, 1, 2], reverse=True) == [5, 4, 3, 2, 1]
