package allocation;

public class FreeList {

	private static class Node {
		public Node previous;
		public Node next;
		public int space;
		public boolean used;
		public int address;
	}
	
	private Node head;
	private Node tail;

	public FreeList(int size) {		
		//TODO: Complete constructor
	}

	public int allocate(int bytes) {
		//TODO: Complete allocate() method
	}
	
	public boolean free(int address) {
		Node temp = head;		
		while(temp != null && temp.address != address)
			temp = temp.next;
		
		if(temp == null || !temp.used)
			return false;
		else {
			temp.used = false;
			// Merge backwards
			while(temp.previous != null && !temp.previous.used) {
				temp.previous.space += temp.space;
				temp.previous.next = temp.next;
				if(temp.next != null)
					temp.next.previous = temp.previous;
				else
					tail = temp.previous;
				temp = temp.previous;
			}
			
			// Merge forwards
			while(temp.next != null && !temp.next.used) {
				temp.space += temp.next.space;
				if(temp.next.next != null)
					temp.next.next.previous = temp;
				else
					tail = temp;
				temp.next = temp.next.next;
			}
			
			return true;
		}		
	}

	public void print() {
		//TODO: Complete print() method
	}	
}