One of the services provided by an operating system is memory management. The OS typically provides an API for allocating and releasing memory in a process's address space. A process should only read and write memory at addresses which have been allocated by the operating system. In this kata you will implement a simulation of a simple memory manager.
The language you will be using has no low level memory API, so for our simulation we will simply use an array as the process address space. The memory manager constructor will accept an array (further referred to as `memory`) where blocks of indices will be allocated later.
___
# Memory Manager Contract
## allocate(size)
`allocate` reserves a sequential block (sub-array) of `size` received as an argument in `memory`. It should return the index of the first element in the allocated block, or throw an exception if there is no block big enough to satisfy the requirements.
## release(pointer)
`release` accepts an integer representing the start of the block allocated ealier, and frees that block. If the released block is adjacent to a free block, they should be merged into a larger free block. Releasing an unallocated block should cause an exception.
## write(pointer, value)
To support testing this simulation our memory manager needs to support read/write functionality. Only elements within allocated blocks may be written to. The `write` method accepts an index in `memory` and a `value`. The `value` should be stored in `memory` at that index if it lies within an allocated block, or throw an exception otherwise.
## read(pointer)
This method is the counterpart to `write`. Only indices within allocated blocks may be read. The `read` method accepts an index. If the `index` is within an allocated block, the value stored in `memory` at that index should be returned, or an exception should be thrown otherwise.
class MemoryManager:
    
    def __init__(self, memory):
        """
        @constructor Creates a new memory manager for the provided array.
        @param {memory} An array to use as the backing memory.
        """
        self.memory = memory
        self.allocationStarts = []
        self.allocationSizes = []

    def allocate(self, size):
        """
        Allocates a block of memory of requested size.
        @param {number} size - The size of the block to allocate.
        @returns {number} A pointer which is the index of the first location in the allocated block.
        @raises If it is not possible to allocate a block of the requested size.
        """
        for i in range(len(self.memory)):
            ok = True
            for j in range(i, i + size): # j is the currently checking index
                if j >= len(self.memory): # it has reached the end
                    ok = False
                    break
                    raise Exception('No allocation available')
#                 if it's already been allocated
                for k in range(len(self.allocationStarts)):
                    if j >= self.allocationStarts[k] and j < self.allocationStarts[k] + self.allocationSizes[k]:
                        ok = False
                        break
            if ok:
                self.allocationStarts.append(i)
                self.allocationSizes.append(size)
#                 print(i)
                return i
        
        # this shouldn't usually be reached because it would stop when j crosses over the length
        raise Exception('No allocation available')
        
        
    
    def release(self, pointer):
        """
        Releases a previously allocated block of memory.
        @param {number} pointer - The pointer to the block to release.
        @raises If the pointer does not point to an allocated block.
        """
        index = self.allocationStarts.index(pointer) # this raises a value error if it's not found
        del self.allocationStarts[index]
        del self.allocationSizes[index]
        

    def read(self, pointer):
        """
        Reads the value at the location identified by pointer
        @param {number} pointer - The location to read.
        @returns {number} The value at that location.
        @raises If pointer is in unallocated memory.
        """
        if len(self.allocationStarts) == 0:
            raise Exception("No memory has been allocated")
            
        for i in range(len(self.allocationStarts)):
            if not(pointer < self.allocationStarts[i] + self.allocationSizes[i] and pointer >= self.allocationStarts[i]):
                raise Exception("Cannot read from unallocated area")
            
        return self.memory[pointer]

    def write(self, pointer, value):
        """
        Writes a value to the location identified by pointer
        @param {number} pointer - The location to write to.
        @param {number} value - The value to write.
        @raises If pointer is in unallocated memory.
        """
        if len(self.allocationStarts) == 0:
            raise Exception("No memory has been allocated")

        for i in range(len(self.allocationStarts)):
            if not(pointer < self.allocationStarts[i] + self.allocationSizes[i] and pointer >= self.allocationStarts[i]):
                raise Exception("Cannot write to unallocated area")
        
        self.memory[pointer] = value
        
        
        
        
        

class MemoryManager:
    
    def __init__(self, memory):
        """
        @constructor Creates a new memory manager for the provided array.
        @param {memory} An array to use as the backing memory.
        """
        self.memory = memory
        self.allocationStarts = []
        self.allocationSizes = []

    def allocate(self, size):
        """
        Allocates a block of memory of requested size.
        @param {number} size - The size of the block to allocate.
        @returns {number} A pointer which is the index of the first location in the allocated block.
        @raises If it is not possible to allocate a block of the requested size.
        """
        for i in range(len(self.memory)):
            ok = True
            for j in range(i, i + size): # j is the currently checking index
                if j >= len(self.memory): # it has reached the end
                    ok = False
                    break
                    raise Exception('No allocation available')
#                 if it's already been allocated
                for k in range(len(self.allocationStarts)):
                    if j >= self.allocationStarts[k] and j < self.allocationStarts[k] + self.allocationSizes[k]:
                        ok = False
                        break
            if ok:
                self.allocationStarts.append(i)
                self.allocationSizes.append(size)
#                 print(i)
                return i
        
        # this shouldn't usually be reached because it would stop when j crosses over the length
        raise Exception('No allocation available')
        
        
    
    def release(self, pointer):
        """
        Releases a previously allocated block of memory.
        @param {number} pointer - The pointer to the block to release.
        @raises If the pointer does not point to an allocated block.
        """
        index = self.allocationStarts.index(pointer) # this raises a value error if it's not found
        del self.allocationStarts[index]
        del self.allocationSizes[index]
        

    def read(self, pointer):
        """
        Reads the value at the location identified by pointer
        @param {number} pointer - The location to read.
        @returns {number} The value at that location.
        @raises If pointer is in unallocated memory.
        """
        if len(self.allocationStarts) == 0:
            raise Exception("No memory has been allocated")
            
        for i in range(len(self.allocationStarts)):
            if not(pointer < self.allocationStarts[i] + self.allocationSizes[i] and pointer >= self.allocationStarts[i]):
                raise Exception("Cannot read from unallocated area")
            
        return self.memory[pointer]

    def write(self, pointer, value):
        """
        Writes a value to the location identified by pointer
        @param {number} pointer - The location to write to.
        @param {number} value - The value to write.
        @raises If pointer is in unallocated memory.
        """
        if len(self.allocationStarts) == 0:
            raise Exception("No memory has been allocated")

        for i in range(len(self.allocationStarts)):
            if not(pointer < self.allocationStarts[i] + self.allocationSizes[i] and pointer >= self.allocationStarts[i]):
                raise Exception("Cannot write to unallocated area")
        
        self.memory[pointer] = value
        
        
        
        
        
