/**
 * Sam Memory: 32-bit wide, implemented as an array of integers.
 * <br>
 * Properties:<br>
 * <ul>
 * <li> Size: MEMORYLIMIT locations (defined in Memory)
 * <li>Each location: 2 integers
 * <ul>
 * <li>Even address in array contain types
 * <li>Odd addresses in array contain data
 * </ul>
 * <li>Each type is a byte (8 bits) but stored as integer
 * <li>Each datum is 32-bits large (integer compatible)
 * <li>Overall array size: INTERNALLIMIT = 2 * MEMORYLIMIT
 */
public class SamMemory implements Memory {
	/* Memory implementation */
	protected final static int INTERNALLIMIT = 20000;
	protected int[] memory = new int[INTERNALLIMIT];
	
	protected Processor cpu;

        /* Garbage collection constants */
        final static int HZONELIMIT = (MEMORYLIMIT - STACKLIMIT) / 2;            //size of 1 zone
        final static int GTHRESHOLD = (int) ((1.0 / 10.0) * (double)HZONELIMIT); //garbage col. threshold
        final static int HZBOUNDARY = (STACKLIMIT + HZONELIMIT);                 //boundary between zones

	/* Heap Active Zone - 0 or 1 */
        private byte activezone = 0;  

	public SamMemory(Sys sys) 
		{ cpu = sys.cpu(); }

	/* Processor access */
	protected final static byte SP = Processor.SP;
	protected final static byte HP = Processor.HP;

	/* Low-level management */
	public void reset() {
		for (int i = 0; i < INTERNALLIMIT; i++)
			memory[i] = 0;
		activezone = 0;
	}

	public int getMem(int pos) throws SystemException {
		if (pos < 0 || pos > MEMORYLIMIT - 1)
			throw new SystemException("getMem(): Invalid memory address: " + pos);
		return memory[2 * pos + 1];
	}

	public byte getType(int pos) throws SystemException {
		if (pos < 0 || pos > MEMORYLIMIT - 1)
			throw new SystemException("getMem(): Invalid memory address: " + pos);
		return (byte)memory[2 * pos];
	}

	public void setMem(int pos, byte type, int value) throws SystemException {
		if (pos < 0 || pos > MEMORYLIMIT - 1)
			throw new SystemException("setMem(): Invalid memory address: " + pos);
		memory[2 * pos] = type;
		memory[2 * pos + 1] = value;
	}

	public void setMem(int pos, int value) throws SystemException 
		{ setMem(pos, INT, value); }

	/* Memory dump */

	public int[] getStack() 
		{ return getMemoryRange(0, cpu.get(SP)); }

	public int[] getHeap() 
		{ return getMemoryRange(STACKLIMIT+1, STACKLIMIT + activezone*HZONELIMIT + 1); }

	public byte[] getStackTypes()
		{ return getTypesRange(0, cpu.get(SP)); }
	
	public byte[] getHeapTypes()
		{ return getTypesRange(STACKLIMIT+1, STACKLIMIT + activezone*HZONELIMIT + 1); }

	public int[] getMemoryRange (int low, int high) {
		final int size = high - low;
		int [] mem = new int[size];
		for (int a=low; a < high; a++)
			mem[a] = memory[a * 2 + 1];
		return mem;
	}

        public byte[] getTypesRange (int low, int high) {
                final int size = high - low;
                byte [] types = new byte[size];
                for (int a=low; a < high; a++)
                        types[a] = (byte)memory[a * 2];
                return types;
        }

	/* Stack zone */
	public int pop() throws SystemException 
		{ return getMem(cpu.dec(SP)); }

	public void push(byte type, int value) throws SystemException {
		setMem(cpu.get(SP), type, value);
		cpu.inc(SP);
	}

	public void push(int value) throws SystemException 
		{ push(INT, value); }

	/* Heap Zones */
	/* The heap grows upwards in each zone - implementation decision. 		    */
	/* Heap Object - definition: one int (type INT) for size + the rest for data    */
	/* Forwarding Pointer - definition: an object signature (location 0) of type MA */

	public void malloc(int size) throws SystemException {

		/* Preliminary calculations */
		int freespace = HZBOUNDARY + HZONELIMIT * activezone - cpu.get(HP) - 1;
		size++; //account for signature

		/* Trigger for garbage collector */
		if (freespace < Math.max(GTHRESHOLD, size)) {
			gcollect();
			freespace = HZBOUNDARY + HZONELIMIT * activezone - cpu.get(HP) - 1; //recalculate
		}

		/* Out of memory check for HP */
		if (freespace < size)
			throw new SystemException("Insufficient heap memory to allocate object of size " + size);

		setMem(cpu.get(HP), INT, size);  //object size signature
		push(MA, cpu.get(HP)); 		 //push the HP  
		cpu.set(HP, cpu.get(HP) + size); //update the HP
	}

	/* Stop - And - Copy tracing garbage collection with breadth-first traversal */

	private void gcollect() throws SystemException {
		/* Preliminary computations */
		final int start = STACKLIMIT + HZONELIMIT * activezone;
		final int end = STACKLIMIT + HZONELIMIT * (activezone + 1);
		final byte newzone = (byte) (activezone == 0 ? 1 : 0);
		final int offset = (newzone - activezone) * HZONELIMIT;
		int move = start + offset; //Last location of moved objects on heap (live zone)
		int scan = start + offset; //Last location scanned for references on heap (live zone)

		/* Move over live objects found on the stack and leave forwarding pointers.. */
		final int limit = cpu.get(SP);
		for (int a = 0; a < limit; a++)
			if (getType(a) == MA && getMem(a) >= start && getMem(a) < end)
				move = update(a, move);

		/* Now keep doing the same in the heap zones until everything's moved */
		while (scan < move) {
			if (getType(scan) == MA && getMem(scan) >= start && getMem(scan) < end)
				move = update(scan, move);
			scan++;
		}

		/* Switch the active zone and update the HP */
		activezone = newzone;
		cpu.set(HP, scan);
	}

	/* Garbage collection helper function */
	/* Takes a pointer and updates it, or moves the object that's there to the live zone 
	   Returns the new position in the live zone.  */
	private int update(int ptr, int pos) throws SystemException {
		int size;
		final int location = getMem(ptr); 			 //see where pointer points

		if (getType(location) == MA) 				 //and if it points to a pointer
			setMem(ptr, MA, getMem(location)); 		 //reroute to proper place
		else { 							 //if it doesn't point to a pointer
			size = getMem(location); 			 //get size of object
			for (int i = location; i < location + size; i++) //move object
				setMem(pos++, getType(i), getMem(i));
			setMem(location, MA, pos - size); 		 //leave forwarding pointer
			setMem(ptr, MA, pos - size); 			 //update the original pointer
		}
		return pos; 						 //return new position
	}
}