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.

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures

Starter code:
def __init__(self, memory):
	

Solutions:
class MemoryManager:

	def __init__(self, memory):
		self.storage = [True] * len(memory)
		self.previous_allocated_index = 0
		self.allocated = {}
		self.data = memory

	def allocate(self, size):
		find_next = self.process_allocate(self.previous_allocated_index, len(self.data) - size + 1, size)
		if find_next is not None:
			return find_next
		from_start = self.process_allocate(0, self.previous_allocated_index - size + 1, size)
		if from_start is not None:
			return from_start
		raise IndexError('caused by insufficient space in storage')

	def process_allocate(self, initial, end, size):
		for i in range(initial, end):
			if all(self.storage[i:i + size]):
				self.previous_allocated_index = i
				self.storage[i:i + size] = [False] * size
				self.allocated[i] = i + size
				return i

	def release(self, pointer):
		if self.storage[pointer]:
			raise RuntimeError('caused by providing incorrect pointer for releasing memory')
		size = self.allocated[pointer] - pointer
		self.storage[pointer:size] = [True] * size
		self.data[pointer:size] = [None] * size
		del self.allocated[pointer]

	def read(self, pointer):
		if self.storage[pointer]:
			raise RuntimeError('caused by providing incorrect pointer for reading memory')
		return self.data[pointer]

	def write(self, pointer, value):
		if self.storage[pointer]:
			raise RuntimeError('caused by providing incorrect pointer for writing memory')
		self.data[pointer] = value


class MemoryManager:

	def __init__(self, memory):
		self.mem = memory
		self.blockpointers = []
		self.blocksizes = []

	def allocate(self, size):
		if size > len(self.mem):
			raise Exception('Cannot allocate more memory than exists')
		if self.blockpointers == [] or (0 not in self.blockpointers and size <= self.blockpointers[0]):
			self.blockpointers.insert(0, 0)
			self.blocksizes.insert(0, size)
			return 0
		for (i, e) in enumerate(self.blocksizes[:-1]):
			if size <= self.blockpointers[i + 1] - self.blockpointers[i] - e:
				self.blockpointers.insert(i, self.blockpointers[i] + e)
				self.blocksizes.insert(i, size)
				return self.blockpointers[i]
		if size <= len(self.mem) - self.blockpointers[-1] - self.blocksizes[-1]:
			self.blockpointers.append(self.blockpointers[-1] + self.blocksizes[-1])
			self.blocksizes.append(size)
			return self.blockpointers[-1]
		raise Exception('Cannot allocate more memory than available')

	def release(self, pointer):
		if pointer not in self.blockpointers:
			raise Exception('No memory has been allocated')
		index = self.blockpointers.index(pointer)
		self.blockpointers.pop(index)
		self.blocksizes.pop(index)
		return

	def read(self, pointer):
		if not self.inMemory(pointer):
			raise Exception('No memory has been allocated')
		return self.mem[pointer]

	def write(self, pointer, value):
		if not self.inMemory(pointer):
			raise Exception('No memory has been allocated')
		self.mem[pointer] = value

	def inMemory(self, pointer):
		i = 0
		while pointer < self.blockpointers[i] + self.blocksizes[i]:
			if pointer >= self.blockpointers[i] and i < self.blockpointers[i] + self.blocksizes[i]:
				return True
			i += 1
		return False


import copy

class MemoryManager:

	def __init__(self, memory: list):
		self.memory = memory
		self.Firstindex = copy.copy(memory)
		self.lens = len(self.Firstindex)

	def allocate(self, size):
		if size > self.lens:
			raise Exception('allocate size ERROR')
		else:
			tempindex = self.Firstindex
			while tempindex:
				if tempindex.count(None) == 0:
					break
				else:
					index = self.Firstindex.index(None)
				if index + size > self.lens:
					break
				else:
					last = index + size
				if self.Firstindex[index:last] == [None] * size:
					self.Firstindex[index:last] = [index] * size
					return index
				else:
					needlist = self.Firstindex[index:last]
					s2 = list(filter(None, needlist))
					tempindex = tempindex[tempindex.index(s2[-1]) + 1:]
			raise Exception('allocate END ERROR')

	def release(self, pointer: int):
		if pointer not in self.Firstindex:
			raise Exception('pointer release ERROR')
		counts = self.Firstindex.count(pointer)
		first = self.Firstindex.index(pointer)
		last = first + counts
		self.memory[first:last] = [None] * counts
		self.Firstindex[first:last] = [None] * counts

	def read(self, pointer):
		if pointer >= self.lens:
			raise Exception('pointer read ERROR1')
		if self.Firstindex[pointer] == None:
			raise Exception('pointer read ERROR2')
		else:
			return self.memory[pointer]

	def write(self, pointer, value):
		if pointer >= self.lens:
			raise Exception()
		if self.Firstindex[pointer] == None:
			raise Exception()
		else:
			self.memory[pointer] = value


class MemoryManager:

	def __init__(self, memory):
		self.memory = memory
		self.allocated = {}
		self.free_memory = {0: len(memory)}

	def allocate(self, size):
		if size > len(self.memory):
			raise 'Cannot allocate more memory than exists'
		for (pointer, block_size) in list(self.free_memory.items()):
			if block_size >= size:
				self.allocated[pointer] = size
				self.free_memory[pointer + size] = block_size - size
				del self.free_memory[pointer]
				return pointer
		raise 'Cannot allocate more memory than available'

	def release(self, pointer):
		self.free_memory[pointer] = self.allocated[pointer]
		del self.allocated[pointer]
		for (p, b_size) in sorted(self.free_memory.items()):
			if self.free_memory.get(p + b_size):
				self.free_memory[p] += self.free_memory[p + b_size]
				del self.free_memory[p + b_size]

	def read(self, pointer):
		for (p, b_size) in list(self.allocated.items()):
			if p <= pointer < p + b_size:
				return self.memory[pointer]
		raise 'No memory has been allocated'

	def write(self, pointer, value):
		for (p, b_size) in list(self.allocated.items()):
			if p <= pointer < p + b_size:
				self.memory[pointer] = value
				return None
		raise 'No memory has been allocated'


class MemoryManager:

	def __init__(self, memory):
		self.memory = memory
		self.available_memory = len(memory)
		self.pointer_list = {0: 0}
		self.pointer = 0

	def allocate(self, size):
		if self.available_memory >= size:
			self.pointer_list[self.pointer] = size
			_pointer = self.pointer
			self.pointer += size
			self.available_memory -= size
			return _pointer
		else:
			raise Exception

	def release(self, pointer):
		free_memory = self.pointer_list[pointer]
		self.available_memory += free_memory
		self.pointer = pointer if pointer < self.pointer else self.pointer
		del self.pointer_list[pointer]

	def read(self, pointer):
		for (p, memory_block) in self.pointer_list.items():
			if pointer <= memory_block:
				return self.memory[pointer]
		raise Exception

	def write(self, pointer, value):
		for (p, memory_block) in self.pointer_list.items():
			if pointer < memory_block:
				self.memory[pointer] = value
				return
		raise Exception


class MemoryManager:

	def __init__(self, memory):
		self._memory = memory
		self._capacity = len(memory)
		self._allocated = {i: False for i in range(self._capacity)}
		self._pointers = dict()

	def allocate(self, size):
		if size > self._capacity:
			raise Exception('Request exceeds max system capacity')
		block_start = self._find_empty_block(size)
		if block_start is None:
			raise Exception('No free block of sufficient size found')
		self._pointers[block_start] = size
		for i in range(size):
			self._allocated[block_start + i] = True
		return block_start

	def release(self, pointer):
		if pointer not in self._pointers:
			raise Exception('Pointer was not allocated')
		pointer_size = self._pointers[pointer]
		for i in range(pointer_size):
			self._allocated[pointer + i] = False
		del self._pointers[pointer]

	def read(self, pointer):
		if not self._allocated[pointer]:
			raise Exception('Memory space not allocated')
		return self._memory[pointer]

	def write(self, pointer, value):
		if not self._allocated[pointer]:
			raise Exception('Cannot write at unallocated memory space')
		self._memory[pointer] = value

	def _find_empty_block(self, size):
		contiguous_size = 0
		index = 0
		start_index = None
		while index < self._capacity:
			if index in self._pointers:
				start_index = None
				size_to_skip = self._pointers[index]
				index = index + size_to_skip
				continue
			else:
				if start_index is None:
					start_index = index
				contiguous_size += 1
				if contiguous_size == size:
					return start_index
				index += 1
		return None


class MemoryManager:

	def __init__(self, memory):
		self.memory = [None] * len(memory)
		self.disk = memory

	def allocate(self, size):
		previous = 0
		for i in range(len(self.memory)):
			if self.memory[i] == None:
				previous += 1
			else:
				previous = 0
			if previous == size:
				start_index = i + 1 - size
				for x in range(start_index, i + 1):
					self.memory[x] = start_index
				return start_index
		raise Exception('No space available')

	def release(self, pointer):
		if pointer not in self.memory:
			raise Exception('pointer not in memory')
		for i in range(len(self.memory)):
			if self.memory[i] == pointer:
				self.memory[i] = None

	def read(self, pointer):
		if self.memory[pointer] == None:
			raise Exception('No space alocated')
		return self.disk[pointer]

	def write(self, pointer, value):
		if self.memory[pointer] == None:
			raise Exception('No space alocated')
		self.disk[pointer] = value


class MemoryManager:

	def __init__(self, memory):
		self.memory = memory
		self.allocationStarts = []
		self.allocationSizes = []

	def allocate(self, size):
		for i in range(len(self.memory)):
			ok = True
			for j in range(i, i + size):
				if j >= len(self.memory):
					ok = False
					break
					raise Exception('No allocation available')
				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)
				return i
		raise Exception('No allocation available')

	def release(self, pointer):
		index = self.allocationStarts.index(pointer)
		del self.allocationStarts[index]
		del self.allocationSizes[index]

	def read(self, pointer):
		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):
		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):
		self.cache = {}
		self.memory = memory

	def allocate(self, size):
		if size > len(self.memory):
			raise Exception('Cannot allocate mory memory than exists')
		elif len(self.cache.items()) == 0:
			self.cache[0] = size - 1
			return 0
		for (start, length) in self.cache.items():
			index = list(self.cache.keys()).index(start)
			next_block = list(self.cache.items())[index + 1] if index + 1 < len(self.cache.items()) else None
			if index == 0 and size - 1 < start:
				self.cache[0] = size - 1
				return 0
			elif next_block and next_block[0] - (start + length + 1) >= size:
				self.cache[start + length + 1] = size - 1
				return start + length + 1
			elif next_block is None and len(self.memory) - (start + length + 1) >= size:
				self.cache[start + length + 1] = size - 1
				return start + length + 1
		raise Exception('Failed to allocate memory')

	def release(self, pointer):
		if pointer not in list(self.cache.keys()):
			raise Exception('Pointer does not point towards allocated block')
		del self.cache[pointer]

	def read(self, pointer):
		if len(self.cache.items()) == 0:
			raise Exception('No memory has been allocated')
		for (start, length) in self.cache.items():
			if pointer not in range(start, start + length):
				raise Exception('Pointer does not point towards allocated block')
		return self.memory[pointer]

	def write(self, pointer, value):
		if len(self.cache.items()) == 0:
			raise Exception('No memory has been allocated')
		for (start, length) in self.cache.items():
			if pointer not in range(start, start + length + 1):
				raise Exception('Pointer does not point towards allocated block')
		self.memory[pointer] = value