# Inf2 - Introduction to Algorithms and Data Structures
# Python lab sheets, Sept-Oct 2019

# LAB SHEET 3: SOLUTIONS TO EXERCISES
# Juan Casanova


import abc

# First, the things that are on the lab sheet that you just have to copy and paste (but we need it).

class Queue(abc.ABC):
	@abc.abstractmethod
	def isEmpty(self):
		pass

	@abc.abstractmethod
	def push(self,x):
		pass

	@abc.abstractmethod
	def pop(self):
		pass


class LL_Queue(Queue):
  def __init__(self):
    self.tail = [()]
    self.head = self.tail
        
  def isEmpty(self):
    return self.head[0] == ()
        
  def push(self,x):
    self.tail[0] = (x,[()])
    self.tail = self.tail[0][1]
        
  def pop(self):
    if self.isEmpty():
      raise IndexError("The queue is empty")
    else:
      y = self.head[0][0]
      self.head = self.head[0][1]
      return y


class BufferedInput:
    def __init__(self,filename,memory): # memory is number of bytes
        self.reader = open(filename,'r',encoding='utf-8')
        self.buffer = self.reader.readlines(memory)
        self.memory = memory
        self.pos = 0
    def readline(self):
        if self.buffer == []:
            return ''
        else:
            result = self.buffer[self.pos]
            self.pos += 1
            if self.pos == len(self.buffer):
                self.buffer = self.reader.readlines(self.memory)
                self.pos = 0
            return result
    def close(self):
        self.reader.close()
	
class BufferedOutput:
    def __init__(self,filename,size): # size is number of lines
        self.writer = open(filename,'w',encoding='utf-8')
        self.buffer = ['' for i in range(size)]
        self.lines = size
        self.pos = 0
    def writeline(self,str):
        self.buffer[self.pos] = str
        self.pos += 1
        if self.pos == self.lines:
            self.writer.writelines(self.buffer)
            self.pos = 0    
    def flush(self): # flushes buffer and closes file
        self.writer.writelines(self.buffer[0:self.pos])
        self.writer.close()

###################################################
# END OF GIVEN CODE
###################################################


# Exercise solutions

# Exercise 1: Circular buffer queue

class CircBuffer_Queue(Queue):
    def __init__(self,n):
        self.size = n
        self.buffer = [()] * n
        self.head = 0
        self.tail = 0
        self.full = False
    def isEmpty(self):
        return (self.head == self.tail and (not self.full))

    def push(self,x):
	# If the buffer is full, raise an error.
	# The buffer is full when the tail is equal to the head before adding an element. This is tricky because this also means that the queue is empty. We need to detect this before-hand on the previous add and save it as a flag.
	# Students were not expected to introduce this error check, it's not an important part of the exercise.
        if self.full:
                raise OverflowError("Trying to push into a full circular buffer")
        else:        
                self.buffer[self.tail] = x
                self.tail = (self.tail + 1) % self.size
                if self.tail == self.head:
                        self.full = True

    def pop(self):
        if self.isEmpty():
      	        raise IndexError("The queue is empty")
        else:
                y = self.buffer[self.head]
                self.head = (self.head + 1) % self.size
                self.full = False
                return y


# Exercise 2.

# The limitation is that it can only contain up to the size of the buffer elements. The linked list implementation does not have this limitation. It does have other small disadvantages. It takes a bit more space in general, but perhaps most importantly, if a queue is going to have a lot of elements added and removed but its size never grows over a certain size, the linked list implementation is going to allocate and free a lot of memory for all the lists that get created and removed, whereas the circular buffer reuses the same space all the time. This would be a noticeable reduction in the speed of the linked list implementation with regards to the circular buffer one, but probably only a constant factor difference, so it would only be relevant in efficiency-critical applications.

# To get rid of the limitation, we need to allow the circular buffer to grow when it's full. In the following implementation, we choose to *duplicate* its size when that happens, but this is an arbitrary choice, other growth factors would work too.

# This is quite tedious to do properly, there are lots of things to take care of.

class CircBuffer_Queue_Growing(Queue):
    def __init__(self,n):
        self.size = n
        self.buffer = [()] * n
        self.head = 0
        self.tail = 0        
    def isEmpty(self):
        return (self.head == self.tail)

    def push(self,x):
        if (self.tail % self.size) == ((self.head + self.size - 1) % self.size):
                # Full buffer. Reallocate into a new buffer.
                # Very importantly, we first need to pad the elements in the queue to the left, so that the head is 0 again.
                # We do this using pop itself. It's the easiest way.
                # This next part could be done more efficiently, by creating the buffer first and then filling it, but this is cleaner to code, and this should not happen often. It won't unless the queue is growing at an exponential speed, and in such a case you have other more worrying problems.
                newbuffer = []
                while not self.isEmpty():
                        e = self.pop()
                        newbuffer.append(e)
                newbuffer.append(x)
                # The magic of lists in Python: we just change the reference of buffer to the buffer we just created.
                self.buffer = newbuffer
                # And make space for the stuff that will come afterwards
                self.buffer.extend([()] * self.size)
                # Don't forget to set the head and tail where it should.
                self.head = 0
                self.tail = self.size                
                self.size = 2 * self.size
        else:
                self.buffer[self.tail] = x
                self.tail = (self.tail + 1) % self.size
        
        

    def pop(self):
        if self.isEmpty():
      	        raise IndexError("The queue is empty")
        else:
                y = self.buffer[self.head]
                self.head = (self.head + 1) % self.size                
                return y


# Exercise 3

def readnumbers1(filename):
	numbers = []
	# The size of the buffer is irrelevant, it will work in any case, but 500 seems like a sensible number (large enough to do one read on small files, small enough to not read too much on large files)
	reader = BufferedInput(filename,500)
	while True:
		line = reader.readline()
		if not line:
			break

		if line[:2] == "N:":
			numbers.append(int(line[2:]))

	reader.close()

	return numbers

# Exercise 4

def readnumbers2(filename):
	numbers = []
	reader = BufferedInput(filename,500)
	while True:
		line = reader.readline()
		if not line:
			break

		if line[:2] == "N:":
			numbers.append(int(line[2:]))
		elif line[:2] == "I:":
			subfile = line[2:-1]
			# Recursive call. We use extend to concatenate the result of the recursive call to the list we already had.
			subnumbers = readnumbers2(subfile)
			numbers.extend(subnumbers)

	reader.close()

	return numbers

# Exercise 5

def readnumbers3(filename):
	numbers = []
	# We keep a queue with the files that need to be read, and we initialise it with the input filename.
	files = LL_Queue()
	files.push(filename)
	# Then we just do a while loop while the queue isn't empty. This is a very usual pattern, and it is essentially breadth-first search (which I believe is part of the course?)
	while not files.isEmpty():
		cur_file = files.pop()
		# Due to no recursive calls, we only have one file open at any given time.
		reader = BufferedInput(cur_file,500)
		while True:
			line = reader.readline()
			if not line:
				break

			if line[:2] == "N:":
				numbers.append(int(line[2:]))
			elif line[:2] == "I:":
				subfile = line[2:-1]
				# Instead of doing a recursive call, we add the other file to the queue of files pending to be read.
				files.push(subfile)

		reader.close()

	return numbers