import java.util.HashMap;
import java.util.LinkedList;
import java.util.Arrays;

/**
 * Implements a simple filesystem. From coursework description: A filesystem is
 * a record, held in memory, of the relationships between directories and files
 * and which disk blocks are allocated to which files. A filesystem consists of
 * directories and files allocated to disk blocks. Directories contain both
 * files and directories, starting at a "root". Only files occupy disk space, in
 * non-contiguous 1KB increments.
 * 
 * Filenames can contain the characters [a-z1-9]+
 * 
 * @author Iain Lane, <a href="mailto:ial05u@cs.nott.ac.uk">ial05u@cs.nott.ac.uk</a>
 * @version 0.6
 */

public class FileSystem {
	
	private Tree fileSystemTree;
	
	/** Stores file->block allocations */
	public static Space fileStorage;

	/**
	 * Ctor - Initialise filesystem with empty root directory and \c m KB of space
	 * 
	 * @param m Amount, in KB, of disk space to allocate
	 *
	 */
	public FileSystem(int m) {
		
		fileSystemTree = new Tree("root");

		fileStorage = new Space(m);
		
	}
	
	/**
	 * Create an empty directory, with path provided in \c name.
	 * 
	 * @param name String array containing path to directory to be created, as in \c file().
	 */
	public void dir(String[] name) throws BadFileNameException {
		
		Tree workingTree = fileSystemTree;
		
		if (name[0] != "root" || (FileExists(name) != null)) {
			
			throw new BadFileNameException();
			
		}
		
		if (DirExists(name) != null) {
			
			return;
			
		}
		
		//loop all the way, creating as we go down if necessary
		for (int i = 0; i < name.length; i++) {
			
			workingTree = workingTree.GetChildByName(name[i]);
			
		}
		
	}
	
	/**
	 * List allocation of blocks on disk.
	 * 
	 * @return A 2D String array of block/file allocations. Each index corresponds to one disk block and the entry is either null 
	 * if the blocks is free or an array of strings which is the path to the file occupying that block.
	 */
	public String[][] disk() {
		
		Leaf[] alloc = FileSystem.fileStorage.getAlloc();
		String[][] disk = new String[alloc.length][];
		int i = 0;
		
		for (Leaf elem : alloc) {
			
			if (elem == null) {
				
				i++;
				continue;
				
			} else {
				
				disk[i++] = elem.getPath();
				
			}
			
		}
		
		return disk;
		
	}
	
	/**
	 * Create a \c k KB file, path provided in name.
	 * 
	 * @param name String array, each element of which is an element in the path to file. 
	 * Must start with root. Any nonexistent directories along the path will be created. 
	 * @param k Size of file to create, in KB.
	 * @throws BadFileNameException First directory is not root.
	 * @throws OutOfSpaceException Adding child failed; not enough free space.
	 */
	public void file(String[] name, int k) throws BadFileNameException, OutOfSpaceException {
		
		Tree workingTree = fileSystemTree;
		String fileName = name[name.length - 1];
		
		if (name[0] != "root") {
			
			throw new BadFileNameException();
			
		}
		
		if (k > FileSystem.fileStorage.countFreeSpace()) { //not enough space free
			
			Leaf file = FileExists(name);
			
			if (file == null) {
			
				throw new OutOfSpaceException();
			
			} else if (k <= (FileSystem.fileStorage.countFreeSpace() - file.allocations.length)) { //if there will be enough space free after deleting the old file, do it
				
				rmfile(name);
				
			}
			
		}
		
		//loop until level containing file
		for (int i = 0; i < name.length - 1; i++) {
			
			workingTree = workingTree.GetChildByName(name[i]);
			
		}
		
		//will now be at same level as file, contained in workingTree
		if (workingTree.children.containsKey(fileName)) { //file exists, remove (reached this point, so file can fit)
			
			if (workingTree.children.get(fileName).getClass().getName() == "Tree") { //name of existing directory 
				
				throw new BadFileNameException();
				
			}
		
			//enough space free, remove old file
			rmfile(name);
			
		}
		
		Leaf newLeaf = new Leaf(fileName, k);
		newLeaf.parent = workingTree;
		newLeaf.depth = newLeaf.parent.depth + 1;
		
		workingTree.children.put(fileName, newLeaf);
		
	}
	
	/**
	 * List files and subdirectories contained in name.
	 * 
	 * @param name String array containing path to directory to list, as in \c file().
	 * @return A String array containing the filename (only) of all files in the directory.
	 */
	public String[] lsdir(String[] name) {
		
		Tree file = DirExists(name);
		String[] fileList;
			
		if (file == null) {
			
			return null;
			
		}

		fileList = new String[file.children.size()];
		fileList = file.children.keySet().toArray(fileList);
		
		//sort array - not essential, but nice!
		Arrays.sort(fileList);
				
		return fileList;
		
	}
	
	/**
	 * Remove a file.
	 * 
	 * @param name String array containing path to file to be removed, as in \c file().
	 * @see file
	 */
	public void rmfile(String[] name) {
		
		Leaf file = FileExists(name);
		
		if (file == null) { //file doesn't exist
			
			return;
			
		}
		
		FileSystem.fileStorage.Dealloc(file);
		
	}
	
	/**
	 * Remove an empty directory.
	 * 
	 * @param name String array containing path to directory to be removed, as in \c file().
	 * @throws DirectoryNotEmptyException The directory is not empty.
	 * @see file
	 */
	public void rmdir(String[] name) throws DirectoryNotEmptyException {
		
		Tree dir = DirExists(name);
		
		if (dir == null) {
			
			return;
			
		}
		
		if (dir.children.size() > 0) {
			
			throw new DirectoryNotEmptyException();
			
		}
		
		dir.parent.children.remove(dir.name);
		
	}

	
	private Node PathExists(String[] name) {
		
		Tree workingTree = fileSystemTree;
		
		for (int i = 0; i < name.length - 1; i++) {
			
			if (!workingTree.children.containsKey(name[i])) {
				
				return null;
				
			}
			
			workingTree = (Tree) workingTree.children.get(name[i]);
			
		}
		
		return workingTree.children.get(name[name.length - 1]);
		
	}
	
	/**
	 * Checks whether the specified file exists
	 * @param name Path to the file
	 * @return File if exists, \c null otherwise
	 */
	public Leaf FileExists(String[] name) {
		
		Node found = PathExists(name);
		
		if (found == null || found.getClass().getName() == "Node") {
			
			return null;
			
		}
		
		return (Leaf) found;
		
	}

	/**
	 * Checks whether the specified directory exists
	 * @param name Path to directory
	 * @return Directory if exists, null otherwise
	 */
	public Tree DirExists(String[] name) {
		
			Node found = PathExists(name);
		
		if (found == null || found.getClass().getName() == "Leaf") {
			
			return null;
			
		}
		
		return (Tree) found;
		
	}
}

/**
 * Leaf - cannot have children.
 * 
 * @author iain
 *
 */
class Leaf extends Node {
	
	/** Size (in KB) of Leaf */
	public int size;
	/** Array of blocks containing Leaf data */
	public int[] allocations;
	
	/**
	 * Ctor - create leaf.
	 * 
	 * @param name Name of the leaf.
	 * @param size Size, in KB, of the leaf.
	 * @throws OutOfSpaceException Allocating space failed.
	 */
	public Leaf(String name, int size) throws OutOfSpaceException {
		
		this.name = name;
		
		allocateSpace(size);
		
	}
	
	private void allocateSpace(int size) throws OutOfSpaceException {
				
		FileSystem.fileStorage.Alloc(size, this);
		
	}

}

/**
 * Class from which Trees and Leaves are derived.
 * Every element is actually a node. 
 * 
 * @author iain
 *
 */
abstract class Node {
	
	/** Every node must have a name */
	String name;
	/** Every node must have a parent. For \c root this will be null */
	public Tree parent;
	/** Store the depth */
	int depth = 0;
	
	/**
	 * Get the path to the current node
	 * @return Path to the current node
	 */
	public String[] getPath() {

		String[] path = new String[this.depth];
		Node workingNode = this;

		for (int i = this.depth - 1; i >= 0; i--) {

			path[i] = workingNode.name;
			workingNode = workingNode.parent;

		}

		return path;

	}

}

/**
 * Implement file storage. Provide methods for allocating and deallocating files on disk.
 * 
 * @author iain
 *
 */
class Space {
	
	private Leaf[] blocks;
	private LinkedList<Integer> freeBlocks;

	/**
	 * Ctor - create \c size blank filesystem blocks.
	 * @param size
	 */
	public Space(int size) {

		blocks = new Leaf[size];
		//sacrifice space for speed
		freeBlocks = new LinkedList<Integer>();
		
		//O(size) to initialize queue
		for (int i = 0; i < size; i++) {
			
			freeBlocks.add(i);
			
		}

	}
	
	/**
	 * Allocate \c size blocks to store \c file.
	 * 
	 * @param size Number of blocks, in KB, required by \c file.
	 * @param file File to store.
	 * @throws OutOfSpaceException
	 */
	public void Alloc(int size, Leaf file) throws OutOfSpaceException {
		
		file.allocations = new int[size];
		
		//we reached this point, therefore there is enough free space
		for (int i = 0; i < size; i++) {
			
			file.allocations[i] = freeBlocks.poll();
			blocks[file.allocations[i]] = file;

		}
		
	}
	
	/**
	 * Free any space occupied by \c file.
	 * 
	 * @param file File to deallocate.
	 */
	public void Dealloc(Leaf file) {
		
		for (int i = 0; i < file.allocations.length; i++) {
			
			blocks[file.allocations[i]] = null;
			//record new free block
			freeBlocks.add(file.allocations[i]);
			
		}
		
		file.parent.children.remove(file.name);
		
	}
	
	/**
	 * Count the amount of free space.
	 * @return the amount of kb blocks free
	 */
	public int countFreeSpace() {
		
		return freeBlocks.size();
		
	}

	/**
	 * Get the file allocations
	 * @return an array (of leaves) of allocations 
	 */
	public Leaf[] getAlloc() {
		
		return blocks;
		
	}
}

/**
 * Tree data structure - nodes can have arbitrarily many children.
 * 
 * @author iain
 * 
 */
class Tree extends Node {
	
	/** The children of the current node */
	public HashMap<String, Node> children = new HashMap<String, Node>();
	

	/**
	 * Ctor - create tree.
	 * 
	 * @param name The name of the root element of this tree.
	 */
	public Tree(String name) {
		
		this.name = name;

	}
	
	/**
	 * Get a child from a \c Node, or create it if nonexistant.
	 * 
	 * @param name Name of child to search for. 
	 * @return Tree found (or created).
	 */
	public Tree GetChildByName(String name) {
		
		if (this.children.containsKey(name)) {
			
			return (Tree) this.children.get(name);
			
		}
		
		//not found - create
		
		Tree newTree = new Tree(name);
		newTree.parent = this;
		newTree.depth = newTree.parent.depth + 1;
		
		this.children.put(name, newTree);
		
		return newTree;
		
	}

}