//--------------------------------------------------------------------
// Class FreeSpaceMgr (FSM)
//
// Purpose  : handle free blocks on disk
//--------------------------------------------------------------------

import java.awt.Font;
import java.awt.Frame;
import java.awt.TextArea;
 
public class FreeSpaceMgr extends Frame
{
	public int maxNoOfFreeBlocks, maxFreeBlockNo;

	private static TextArea theDisplay;
	private static String fileContent;
	private static int currBlockNo, currIndex;


//--------------------------------------------------------------------
// Contructor for FreeSpaceMgr(1)
//
// Input	: content of file
// Output   : None
// Purpose  : contructing the free space environment
//--------------------------------------------------------------------

	FreeSpaceMgr (String fileContent)
	{
		super ("Free Space Manager");
		int endIndex = fileContent.indexOf("(9999,");
		endIndex = fileContent.indexOf(")", endIndex);
		this.fileContent = fileContent.substring(0, endIndex + 2);

		theDisplay = new TextArea ();
		add ("Center", theDisplay );
		theDisplay.setEditable (false);
		theDisplay.setFont(new Font("Monospaced", Font.PLAIN, 17));
		setSize(720, 320);		
		show();
		toFront();
		theDisplay.setText(this.fileContent);
	}


//--------------------------------------------------------------------
// Contructor for FreeSpaceMgr(2)
//
// Input	: content of file
// Output   : None
// Purpose  : contructing the free space environment during Format
//--------------------------------------------------------------------

	FreeSpaceMgr (int noOfBlocks)
	{
		this.fileContent = "(3," + Integer.toString(noOfBlocks - 3) + ")\n"
			  + "(9999," + Integer.toString(noOfBlocks - 3) + ")\n";
		theDisplay.setText(this.fileContent);
	}


//--------------------------------------------------------------------
// Method getContent
//
// Input	: None
// Output   : free space manager content
// Purpose  : to free space manager Content
//--------------------------------------------------------------------

	public String getContent ()
	{
		return fileContent;
	}


//--------------------------------------------------------------------
// Method getNoOfFreeBlocks
//
// Input	: None
// Output   : NoOfFreeBlocks
// Purpose  : to get NoOfFreeBlocks of disks
//--------------------------------------------------------------------

	public int getNoOfFreeBlocks ()
	{
		return getValue(9999);
	}


//--------------------------------------------------------------------
// Method setNoOfFreeBlocks
//
// Input	: None
// Output   : None
// Purpose  : to set NoOfFreeBlocks of disks
//--------------------------------------------------------------------

	private void setNoOfFreeBlocks (int noOfFreeBlocks)
	{
		setValue(9999, noOfFreeBlocks);
		return ;
	}


//--------------------------------------------------------------------
// Method firstFit
//
// Input	: noOfBlocks requested
// Output   : the first contiguous block no
// Purpose  : to get the firstfit for noOfBlocks.  If not found the
//            the bestFit will be returned.
//--------------------------------------------------------------------

	public int firstFit (int noOfBlocks) 
		throws NotEnoughSpaceException
	{
		int noOfFreeBlocks = getNoOfFreeBlocks ();
		if (noOfBlocks > noOfFreeBlocks) 
			throw new NotEnoughSpaceException
			(noOfBlocks, noOfFreeBlocks);

		int blocks;
		maxNoOfFreeBlocks = 0;
		maxFreeBlockNo = 0;
		currBlockNo = 0;
		getNext();
		while ( currBlockNo < 9999 )
		{
			// free space found
			blocks = getValue(currBlockNo);
			if ( blocks >= noOfBlocks)
			{
				return currBlockNo;
			}			 

			maxFreeBlockNo = maxNoOfFreeBlocks > blocks ? 
							 maxFreeBlockNo : currBlockNo;
			maxNoOfFreeBlocks = maxNoOfFreeBlocks > blocks ? 
								maxNoOfFreeBlocks : blocks;
			getNext();
		}

		return -1;
	}


//--------------------------------------------------------------------
// Method take
//
// Input	: blockNo, noOfBlocks
// Output   : flag show status of taking free blocks
// Purpose  : to acquire the free blocks from the pool
//--------------------------------------------------------------------

	public boolean take (int blockNo, int noOfBlocks)
	{
		boolean flag = deleteEntry (blockNo, noOfBlocks);
		theDisplay.setText(fileContent);
		return flag;
	}


//--------------------------------------------------------------------
// Method free
//
// Input	: blockNo, noOfBlocks
// Output   : flag show status of freeing blocks
// Purpose  : to put the free blocks back to the pool
//--------------------------------------------------------------------

	public boolean free (int blockNo, int noOfBlocks)
	{
		boolean flag;
		if (blockNo <= 0) return false;
		flag = newEntry (blockNo, noOfBlocks);
		theDisplay.setText(fileContent);
		return flag;
	}


//--------------------------------------------------------------------
// Method defragOK
//
// Input	: none
// Output   : flag show status of defrag OK
// Purpose  : to indicate the final state of defragmentation
//--------------------------------------------------------------------

	public boolean defragOK (int noOfBlocks)
	{
		boolean flag;
		int noOfFreeBlocks = getNoOfFreeBlocks();

		if (noOfFreeBlocks == 0) return true;

		return (getValue(noOfBlocks - noOfFreeBlocks) == noOfFreeBlocks);
	}


//--------------------------------------------------------------------
// Method isFree
//
// Input	: blockNo
// Output   : the earliest free block in that group else "-1"
// Purpose  : to check if the block is free
//--------------------------------------------------------------------

	private int isFree (int blockNo)
	{
		currBlockNo = 0;
		int tmpBlockNo = -1;

		getNext();

		// that block is even before the first record
		if (currBlockNo > blockNo) return -1;

		// there is no free blocks listed
		if (currBlockNo >= 9999) return -1;

		while ( currBlockNo < blockNo )
		{
			tmpBlockNo = currBlockNo;
			getNext();
		}

		// that block is free and it is the head of the record
		if (currBlockNo == blockNo) return blockNo;

		currBlockNo = tmpBlockNo;
		if ( (currBlockNo + getValue(currBlockNo) - 1) >= blockNo) 
			return currBlockNo;
		return -1;
	}


//--------------------------------------------------------------------
// Method getNext
//
// Input	: none
// Output   : none
// Purpose  : to iterate to next records
//--------------------------------------------------------------------

	private void getNext ()
	{
		String tmpString;
		if (currBlockNo == 0)
		{
			currIndex = fileContent.indexOf(",", 0);
			if (currIndex == -1) { currBlockNo = -1; return; }
			tmpString = fileContent.substring(1, currIndex);
		}
		else
		{
			currIndex = fileContent.indexOf(",", currIndex + 1);
			if (currIndex == -1)  { currBlockNo = -1; return; }
			int beginIndex = fileContent.lastIndexOf("(", currIndex);
			tmpString = fileContent.substring(beginIndex + 1, currIndex);
		}

		currBlockNo = Integer.parseInt(tmpString);
		return;
	}


//--------------------------------------------------------------------
// Method deleteEntry
//
// Input	: blockNo, noOfBlocks
// Output   : status if deletion is successful
// Purpose  : to delete the free blocks from the pool
//--------------------------------------------------------------------

	private boolean deleteEntry (int blockNo, int noOfBlocks)
	{
		int blocks = getValue(blockNo);

		if ( noOfBlocks > blocks ) return false;
		int beginIndex = fileContent.indexOf("(" + Integer.toString(blockNo) + ",");
		int endIndex = fileContent.indexOf("(", beginIndex + 1);
		String tmpString;
		if ( noOfBlocks == blocks )
		{
			tmpString = fileContent.substring(0, beginIndex)
						+ fileContent.substring(endIndex);
		}
		else
		{
			tmpString = fileContent.substring(0, beginIndex)
						+ "("
						+ Integer.toString(blockNo + noOfBlocks)
						+ ","
						+ Integer.toString(blocks - noOfBlocks)
						+ ")\n"
						+ fileContent.substring(endIndex);
		}

		fileContent = new String(tmpString);
		setNoOfFreeBlocks(getNoOfFreeBlocks() - noOfBlocks);
		return true;
	}


//--------------------------------------------------------------------
// Method newEntry
//
// Input	: blockNo, noOfBlocks
// Output   : status if insertion is successful
// Purpose  : to insert new free blocks into the pool
//--------------------------------------------------------------------
	
	private boolean newEntry (int blockNo, int noOfBlocks)
	{
		int beginIndex, endIndex;
		String tmpString;
		int prevBlockNo = isFree(blockNo - 1);
		int prevNoOfBlocks = getValue(prevBlockNo);
		int nextBlockNo = isFree(blockNo + noOfBlocks);
		int nextNoOfBlocks = getValue(nextBlockNo);

		// between 2 group of free blocks
		if ( (prevBlockNo != -1) && (nextBlockNo != -1) )
		{
			deleteEntry(nextBlockNo, nextNoOfBlocks);
			setValue(prevBlockNo, prevNoOfBlocks + noOfBlocks + nextNoOfBlocks);
			setNoOfFreeBlocks(getNoOfFreeBlocks() + noOfBlocks + nextNoOfBlocks); 
		}	 
		else if (prevBlockNo != -1)
		{
			// can merge with the previous records
			setValue(prevBlockNo, noOfBlocks + prevNoOfBlocks);
			setNoOfFreeBlocks(getNoOfFreeBlocks() + noOfBlocks); 
		}
		else if (nextBlockNo != -1)
		{
			// can merge with the next records
			deleteEntry(nextBlockNo, nextNoOfBlocks);
			return newEntry (blockNo, noOfBlocks + nextNoOfBlocks);
		}
		else
		{
			// not close to any free blocks, insert new entry
			currBlockNo = 0;
			getNext();
			while ( currBlockNo < blockNo ) getNext();
			beginIndex = fileContent.indexOf("(" + Integer.toString(currBlockNo) + ",");
			tmpString = fileContent.substring(0, beginIndex)
						+ "("
					    + Integer.toString(blockNo)
					    + ","
					    + Integer.toString(noOfBlocks)
						+ ")\n"
					    + fileContent.substring(beginIndex);
			fileContent = new String();
			fileContent = tmpString;
			setNoOfFreeBlocks(getNoOfFreeBlocks() + noOfBlocks); 
		}
		return true;
	}


//--------------------------------------------------------------------
// Method setValue
//
// Input	: blockNo, noOfBlocks
// Output   : none
// Purpose  : set value of certain free blocks group
//--------------------------------------------------------------------

	private void setValue (int blockNo, int noOfBlocks)
	{
		int beginIndex, endIndex;
		if ( (beginIndex = fileContent.indexOf("(" + Integer.toString(blockNo) + ","))
			== -1 )	return;
		beginIndex = fileContent.indexOf(",", beginIndex);
		endIndex = fileContent.indexOf(")\n", beginIndex);
		String tmpString;
		tmpString = fileContent.substring(0, beginIndex + 1)
					+ Integer.toString(noOfBlocks)
					+ fileContent.substring(endIndex);
		fileContent = new String();
		fileContent = tmpString;
		return ;
	}


//--------------------------------------------------------------------
// Method getValue
//
// Input	: blockNo
// Output   : none
// Purpose  : to get how many free blocks in that group
//--------------------------------------------------------------------

	private int getValue (int blockNo)
	{
		int beginIndex, endIndex;
		if ( (beginIndex = fileContent.indexOf("(" + Integer.toString(blockNo) + ","))
			== -1 )	return -1;
		beginIndex = fileContent.indexOf(",", beginIndex);
		endIndex = fileContent.indexOf(")\n", beginIndex);
		return Integer.parseInt(fileContent.substring(beginIndex + 1, endIndex));
	}

}


//--------------------------------------------------------------------
// End Class FreeSpaceMgr
//--------------------------------------------------------------------