





from collections import deque


class 						lowerCamelCase       :







							"""simple docstring"""




							def __init__( self     :					int,			_UpperCAmelCase     :					str,			_UpperCAmelCase     :					int,			_UpperCAmelCase     :					int						)				->			None:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      List[Any]     =						process_name  # process name
														SCREAMING_SNAKE_CASE__       :      List[Any]     =						arrival_time  # arrival time of the process
														# completion time of finished process or last interrupted time
														SCREAMING_SNAKE_CASE__       :      str     =						arrival_time
														SCREAMING_SNAKE_CASE__       :      Dict     =						burst_time  # remaining burst time
														SCREAMING_SNAKE_CASE__       :      List[Any]     =						0  # total time of the process wait in ready queue
														SCREAMING_SNAKE_CASE__       :      List[str]     =						0  # time from arrival time to completion time


class 						lowerCamelCase       :







							"""simple docstring"""




							def __init__( self     :					Dict,			_UpperCAmelCase     :					int,			_UpperCAmelCase     :					list[int],			_UpperCAmelCase     :					deque[Process],			_UpperCAmelCase     :					int,			)				->			None:





														"""simple docstring"""
														# total number of mlfq's queues
														SCREAMING_SNAKE_CASE__       :      Dict     =						number_of_queues
														# time slice of queues that round robin algorithm applied
														SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						time_slices
														# unfinished process is in this ready_queue
														SCREAMING_SNAKE_CASE__       :      Optional[int]     =						queue
														# current time
														SCREAMING_SNAKE_CASE__       :      List[str]     =						current_time
														# finished process is in this sequence queue
														SCREAMING_SNAKE_CASE__       :      deque[Process]     =						deque()






							def  A_     ( self     :					List[str]						)				->			list[str]:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      int     =						[]
														for i in range(len(self.finish_queue						)						):
																					sequence.append(self.finish_queue[i].process_name						)
														return sequence






							def  A_     ( self     :					Optional[Any],			_UpperCAmelCase     :					list[Process]						)				->			list[int]:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      Dict     =						[]
														for i in range(len(_UpperCAmelCase						)						):
																					waiting_times.append(queue[i].waiting_time						)
														return waiting_times






							def  A_     ( self     :					Tuple,			_UpperCAmelCase     :					list[Process]						)				->			list[int]:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      Tuple     =						[]
														for i in range(len(_UpperCAmelCase						)						):
																					turnaround_times.append(queue[i].turnaround_time						)
														return turnaround_times






							def  A_     ( self     :					Tuple,			_UpperCAmelCase     :					list[Process]						)				->			list[int]:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      Any     =						[]
														for i in range(len(_UpperCAmelCase						)						):
																					completion_times.append(queue[i].stop_time						)
														return completion_times






							def  A_     ( self     :					Tuple,			_UpperCAmelCase     :					deque[Process]						)				->			list[int]:





														"""simple docstring"""
														return [q.burst_time for q in queue]






							def  A_     ( self     :					Dict,			_UpperCAmelCase     :					Process						)				->			int:





														"""simple docstring"""
														process.waiting_time += self.current_time - process.stop_time
														return process.waiting_time






							def  A_     ( self     :					Any,			_UpperCAmelCase     :					deque[Process]						)				->			deque[Process]:





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

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






							def  A_     ( self     :					List[str],			_UpperCAmelCase     :					deque[Process],			_UpperCAmelCase     :					int						)				->			tuple[deque[Process], deque[Process]]:





														"""simple docstring"""
														SCREAMING_SNAKE_CASE__       :      deque[Process]     =						deque()  # sequence deque of terminated process
														# just for 1 cycle and unfinished processes will go back to queue
														for _ in range(len(_UpperCAmelCase						)						):
																					SCREAMING_SNAKE_CASE__       :      Optional[Any]     =						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(_UpperCAmelCase						)
																					# 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
																												SCREAMING_SNAKE_CASE__       :      Tuple     =						self.current_time
																												# locate the process behind the queue because it is not finished
																												ready_queue.append(_UpperCAmelCase						)
																					else:
																												# use CPU for remaining burst time
																												self.current_time += cp.burst_time
																												# set burst time 0 because the process is finished
																												SCREAMING_SNAKE_CASE__       :      Dict     =						0
																												# set the finish time
																												SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						self.current_time
																												# update the process' turnaround time because it is finished
																												SCREAMING_SNAKE_CASE__       :      int     =						self.current_time - cp.arrival_time
																												# add the process to queue that has finished queue
																												finished.append(_UpperCAmelCase						)

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






							def  A_     ( self     :					Optional[Any]						)				->			deque[Process]:





														"""simple docstring"""

														#  all queues except last one have round_robin algorithm
														for i in range(self.number_of_queues - 1						):
																					SCREAMING_SNAKE_CASE__   ,SCREAMING_SNAKE_CASE__       :      Dict     =						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 :    Tuple  							= Process('''P1''', 0, 5_3)
		_lowerCamelCase :    Optional[int]  							= Process('''P2''', 0, 1_7)
		_lowerCamelCase :    Any  							= Process('''P3''', 0, 6_8)
		_lowerCamelCase :    int  							= Process('''P4''', 0, 2_4)
		_lowerCamelCase :    Tuple  							= 3
		_lowerCamelCase :    List[Any]  							= [1_7, 2_5]
		_lowerCamelCase :    Optional[int]  							= 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 :    Union[str, Any]  							= Process('''P1''', 0, 5_3)
		_lowerCamelCase :    List[str]  							= Process('''P2''', 0, 1_7)
		_lowerCamelCase :    int  							= Process('''P3''', 0, 6_8)
		_lowerCamelCase :    Optional[int]  							= Process('''P4''', 0, 2_4)
		_lowerCamelCase :    Optional[int]  							= 3
		_lowerCamelCase :    int  							= [1_7, 2_5]
		_lowerCamelCase :    Any  							= deque([Pa, Pa, Pa, Pa])
		_lowerCamelCase :    str  							= MLFQ(number_of_queues, time_slices, queue, 0)
		_lowerCamelCase :    Dict  							= 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()}"
		)













from queue import PriorityQueue
from typing import Any

import numpy as np




def _a (  SCREAMING_SNAKE_CASE__      :  dict			,				SCREAMING_SNAKE_CASE__      :  str			,				SCREAMING_SNAKE_CASE__      :  set			,				SCREAMING_SNAKE_CASE__      :  set			,				SCREAMING_SNAKE_CASE__      :  dict			,				SCREAMING_SNAKE_CASE__      :  dict			,				SCREAMING_SNAKE_CASE__      :  PriorityQueue			,				SCREAMING_SNAKE_CASE__      :  dict			,				SCREAMING_SNAKE_CASE__      :  float | int			,				)	->    float | int:

							'''simple docstring'''






							for nxt, d in graph[v]:
														if nxt in visited_forward:
																					continue
														SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						cst_fwd.get(SCREAMING_SNAKE_CASE__			,				np.inf       )
														SCREAMING_SNAKE_CASE__       :      Optional[int]     =						cst_fwd[v] + d
														if new_cost_f < old_cost_f:
																					queue.put((new_cost_f, nxt)       )
																					SCREAMING_SNAKE_CASE__       :      List[Any]     =						new_cost_f
																					SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						v
														if nxt in visited_backward:
																					if cst_fwd[v] + d + cst_bwd[nxt] < shortest_distance:
																												SCREAMING_SNAKE_CASE__       :      Optional[int]     =						cst_fwd[v] + d + cst_bwd[nxt]
							return shortest_distance




def _a (  SCREAMING_SNAKE_CASE__      :  str			,				SCREAMING_SNAKE_CASE__      :  str			,				SCREAMING_SNAKE_CASE__      :  dict			,				SCREAMING_SNAKE_CASE__      :  dict       )	->    int:

							'''simple docstring'''






							SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						-1

							SCREAMING_SNAKE_CASE__       :      List[str]     =						set()
							SCREAMING_SNAKE_CASE__       :      List[Any]     =						set()
							SCREAMING_SNAKE_CASE__       :      int     =						{source: 0}
							SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						{destination: 0}
							SCREAMING_SNAKE_CASE__       :      List[Any]     =						{source: None}
							SCREAMING_SNAKE_CASE__       :      Union[str, Any]     =						{destination: None}
							SCREAMING_SNAKE_CASE__       :      PriorityQueue[Any]     =						PriorityQueue()
							SCREAMING_SNAKE_CASE__       :      PriorityQueue[Any]     =						PriorityQueue()

							SCREAMING_SNAKE_CASE__       :      Dict     =						np.inf

							queue_forward.put((0, source)       )
							queue_backward.put((0, destination)       )

							if source == destination:
														return 0

							while not queue_forward.empty() and not queue_backward.empty():
														SCREAMING_SNAKE_CASE__   ,SCREAMING_SNAKE_CASE__       :      List[str]     =						queue_forward.get()
														visited_forward.add(SCREAMING_SNAKE_CASE__       )

														SCREAMING_SNAKE_CASE__   ,SCREAMING_SNAKE_CASE__       :      List[Any]     =						queue_backward.get()
														visited_backward.add(SCREAMING_SNAKE_CASE__       )

														SCREAMING_SNAKE_CASE__       :      Any     =						pass_and_relaxation(
														    SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				)

														SCREAMING_SNAKE_CASE__       :      List[Any]     =						pass_and_relaxation(
														    SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				SCREAMING_SNAKE_CASE__			,				)

														if cst_fwd[v_fwd] + cst_bwd[v_bwd] >= shortest_distance:
																					break

							if shortest_distance != np.inf:
														SCREAMING_SNAKE_CASE__       :      int     =						shortest_distance
							return shortest_path_distance


_lowerCamelCase :    Optional[Any]  							= {
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''G''', 2]],
    '''F''': [],
    '''G''': [['''F''', 1]],
}
_lowerCamelCase :    Tuple  							= {
    '''B''': [['''E''', 1]],
    '''C''': [['''B''', 1]],
    '''D''': [['''C''', 1]],
    '''F''': [['''D''', 1], ['''G''', 1]],
    '''E''': [[None, np.inf]],
    '''G''': [['''E''', 2]],
}

if __name__ == "__main__":
		import doctest

		doctest.testmod()






