buddy

"""
@Buddy System Implementation
    CHOO SANGBUEM
    71675619
"""
"""
     level: 0 1 2 3 4  5  |6
     size:  1 2 4 8 16 32 |64

     Level 6 can only belong to the actual memory itself
    So we can start at var level = 5
     thus, partition size = 2^level, where every time partition happens, level -= 1

     Two blocks are said to be companion buddies if they resulted from
    the split of the same direct parent block

    parent = a number gets assigned every time partition happens.
"""

class Partition:
    def __init__(self, data, start, size, parent, state="free"):
        self.data = data
        self.start = start
        self.size = size
        self.parent = parent
        self.state = state

        self.prev = None
        self.next = None

class Memory(): #doubly linked list implementation

    memory_size = 64
    parent = 1

    def __init__(self):
        self.head = self.tail = Partition(0, 0, self.memory_size, 0)

    # Show the memory state
    # def showMem(self):
    #     #show graphically

    def makePartition(self, currPart):
        #halve current partition size
        currPart.size = currPart.size / 2
        #make new partition object starting from second half
        newStart = currPart.start + currPart.size
        newPart = Partition(0, newStart, currPart.size, 0)
        #assign parent number
        currPart.parent = newPart.parent = self.parent
        #increase the parent number
        self.parent += 1

        #insert the newPart in a doubly linked list
        newPart.next = currPart.next
        currPart.next = newPart
        if newPart.next is not None:
            newPart.next.prev = newPart
            newPart.prev = currPart

        #head will always stay the same since we are making new partition to the right of original
        #set tail
        while newPart.next is not None:
            newPart = newPart.next
        self.tail = newPart

        print(newPart.size)

        return currPart # newly halved one

    def allocate(self, input_size):

        # find the smallest possible free partition by traversing backward,
        currPart = self.tail

        while currPart.prev:
            if(currPart.prev.state is "free" and currPart.prev.size >= input_size):
                currPart = currPart.prev

        #check first partition
        if currPart.state is "free" and currPart.size >= input_size:
                pass
        # in case nothing new found, check the current partition's state
        elif currPart.state is not "free":
            print("ALl memory is used.")
            return
        elif currPart.state is "free" and currPart.size < input_size:
            print("Not enough free space.")
            return


        # Now with the free memory found
        # Make more partitions while input is smaller than currPart/2
        while input_size  <= (currPart.size/2):
            currPart = self.makePartition(currPart) #returns first half of the new partition
            #this repeats until the new partition /2 is less than the input

        #finally when all conditions are met, allocate the memory
        currPart.data = input_size
        currPart.state = "allocated"


    def free(self, address):
        #find the partition
        currPart = self.head
        while currPart.next:
            if currPart.start == address:
                #free the memory
                currPart.data = 0
                currPart.state = "free"
                self.merge(currPart)
                return
            currPart = currPart.next
        #last partition
        if currPart.start == address:
            currPart.data = 0
            currPart.state = "free"
            self.merge(currPart)
            return

        print()

    def checkBuddy(self, p1, p2):
        # do they have same parent
        if p1.parent is p2.parent:
            return True
        else:
            return False

    def merge(self, reqPart):
        buddy = None
        #check partitions nearby to see if free
        if reqPart.prev:
            if reqPart.prev.state is "free":
                if self.checkBuddy(reqPart, reqPart.prev):
                    buddy = reqPart.prev
        if reqPart.next:
            if reqPart.next.state is "free":
                if self.checkBuddy(reqPart, reqPart.next):
                    buddy = reqPart.next
        # if buddy found, merge
        if buddy:
            self.delete(buddy)
            reqPart.size = reqPart.size * 2
            #call recursively
            self.merge(reqPart)

        return


    def delete(self, partDel):
        if self.head is partDel:
            self.head = self.head.next
            self.head.prev = None

        elif self.tail == partDel:
            self.tail = self.tail.prev
            self.tail.next = None

        else:
            partDel.prev.next = partDel.next
            partDel.next.prev = partDel.prev

        return



while True:

    # Main
    memory = Memory()

    # Take user input

    # inputs:  [command,num]
    # allocate: a [number of blocks]
    # free:     f [first block number of the allocated chunk]
    # quit:     q

    #split and store
    inputs = input("command, num: ").split(" ")

    if inputs[0] is "a":
        memory.allocate(int(inputs[1]))
        print(memory.head.size)


    elif inputs[0] is "f":
        memory.free(inputs[1])


    elif inputs[0] is "q":
        exit()

    else:
        print("Invalid input")