# -*- coding: utf-8 -*- 

# Node 클래스 정의
class Node:
    def __init__(self, pnum, psize):
        self.pnum = pnum
        self.psize = psize
        self.next = None


# 자료구조 정의
class MemoryList:
    total_memory = 1000.0
    available_memory = total_memory

    # 초기화 메소드
    def __init__(self):
        dummy = Node(0,0.0)
        self.head = dummy
        self.tail = dummy

        self.current = None
        self.before = None
        self.alloc_ptr = None
        self.searching_ptr = None
        self.hole = 0
        self.hole_found = None

        self.num_of_data = 0

        # self.allocMemory(0,self.total_memory)

    # allocMemory 메소드
    def allocMemory(self, pnum, psize):

        if(psize != 0) :

            if(self.available_memory<psize) :
                print("Not enough memory!")
            
            # 처음인 경우 그냥 넣고
            elif((self.num_of_data == 0)or(self.hole==0)) :
                new_node = Node(pnum, psize)
                self.available_memory -= psize
                self.tail.next = new_node
                self.tail = new_node

                self.num_of_data += 1

            # 첫 할당이 아닐 경우는 alloc_ptr 초기화 해서 사용합니다.
            else :
                self.first()
                self.alloc_ptr = self.current
                self.searching_ptr = self.current

                # best를 찾기 위한 변수
                best_fit = 10000
                self.hole_found = False

                while(True) :
                    # pnum = 0(빈자리) 중 psize보다 큰 자리가 있으면
                    if((self.searching_ptr.pnum==0)and(self.searching_ptr.psize>=psize)) :
                        self.hole_found = True
                        # best fit 계산해보고, alloc_ptr 설정
                        if(best_fit>(self.searching_ptr.psize-psize)) :
                            best_fit = self.searching_ptr.psize-psize
                            self.alloc_ptr = self.searching_ptr


                    # 마지막까지 갔으면 break!
                    if(self.searching_ptr.next == None) :
                        self.searching_ptr = None
                        break
                    self.searching_ptr = self.searching_ptr.next

                if(self.hole_found == True) :
                    # new_node를 뒤에 붙일 노드로 초기화
                    new_node = Node(0, (self.alloc_ptr.psize-psize))

                    new_node.next = self.alloc_ptr.next
                    self.alloc_ptr.next = new_node

                    self.alloc_ptr.pnum = pnum
                    self.alloc_ptr.psize = psize

                    if(new_node.psize == 0) :
                        self.alloc_ptr.next = new_node.next
                        new_node.next = None

                    self.available_memory -= psize
                    self.num_of_data += 1

                elif(self.hole_found == False) : 

                    new_node = Node(pnum, psize)
                    self.tail.next = new_node
                    self.tail = new_node
                    self.available_memory -= psize
                    self.num_of_data += 1



        
        elif(psize == 0) :
            self.first()
            while(True) :
                if(self.current.pnum == pnum) :
                    self.current.pnum = 0
                    self.available_memory += self.current.psize
                    self.hole += 1
                    break
                else :
                    self.next()

    
    # def delete(self):
    #     # pop_pnum = self.current.pnum
    #     # pop_psize = self.current.psize

    #     if self.current is self.tail:
    #         self.tail = self.before

    #     self.before.next = self.current.next
    #     self.current = self.before # 중요 : current가 next가 아닌 before로 변경된다.
    #     #

    #     self.num_of_data -= 1

        # return pop_pnum, pop_psize

    # first 메소드 (search1 - 맨 앞의 노드 검색, before, current 변경)
    def first(self):
        if self.num_of_data == 0: # 데이터가 없는 경우 첫번째 노드도 없기 때문에 None 리턴
            return None

        self.before = self.head
        self.current = self.head.next

        # return self.current.psize, self.current.pnum

    # next 메소드 (search2 - current 노드의 다음 노드 검색, 이전에 first 메소드가 한번은 실행되어야 함)
    def next(self):
        if self.current.next == None:
            # print ("End")
            return None

        else :
            self.before = self.current
            self.current = self.current.next

        return self.current.pnum, self.current.psize

    def size(self):
        return self.num_of_data








myMemory = MemoryList()


# 파일 open & process 할당.
f = open('processes.txt','r')
i = 1
print("\n[Memory Size : 1000.0]\n")

while(True) :
    line = f.readline().strip().split()
    if(not line) : break
    
    myMemory.allocMemory(int(line[0]), float(line[1]))
    
    myMemory.first()

    print("REQUEST#"+str(i)+" - Process#"+str(line[0])+" "+str(line[1]))
    while(True) :
        if(myMemory.current.pnum!=0) :
            print("Process#" + str(myMemory.current.pnum) + ": " + str(myMemory.current.psize))
        else :
            print("     Hole: "+str(myMemory.current.psize))
        
        if(myMemory.next()==None) :
            break

    print("Available Memory: "+str(myMemory.available_memory)+"\n")
    i += 1


# print(pdict)
f.close()



# ---------- Testing ----------#

# myMemory.allocMemory(1,22.0)
# myMemory.allocMemory(2,18.0)
# myMemory.allocMemory(3,28.0)
# myMemory.allocMemory(5,25.0)
# myMemory.allocMemory(4,5.0)
# myMemory.allocMemory(2,0)
# myMemory.allocMemory(6,10.0)
# # myMemory.allocMemory(4,0)
# myMemory.allocMemory(5,0)
# myMemory.allocMemory(7,20.0)




# print("MEMORY SIZE: "+str(myMemory.total_memory)+"\n")

# print("REQUEST 1: 22.0")
# print("Best Fit: Allocated at address "+str(myMemory.current.psize))
# print("          "+str(myMemory.available_memory)+" free")