package Sequenic.T2.Coverage;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Map;
import java.util.Set;

public final class TrieSensor {

	//Cache of entry blocks for each method
	private static final Map<String, ObservedBlock> entryBlocks = new HashMap<String, ObservedBlock>();
	private static final ArrayList<String> enteredMethodsList = new ArrayList<String>();
	private static final IdentityHashMap<ObservedBlock, BasicPath> bpCache = new IdentityHashMap<ObservedBlock, BasicPath>();
	
	/**Call on method entry. Returns a TrieSensor Object which can be used to record the path followed
	 * in the given method. 
	 * This method implicitly ticks block with id 0 (the method entry block). 
	 * 
	 * @param methodUname
	 * @return
	 */
	public static ObservedBlock enterMethod(String methodUname)
	{
		synchronized (entryBlocks)
		{
			ObservedBlock root = entryBlocks.get(methodUname);
			if(root==null) {
				entryBlocks.put(methodUname, root = new ObservedBlock(1,null));//(id 0 << 1) + tick bit = 1 
				enteredMethodsList.add(methodUname);
			} else if (root.tickIfUnticked()) {
				enteredMethodsList.add(methodUname);
			}
			return root;
		}
	}
	
	/** Same as clear() but returns all observed BasicPaths.
	 *
	 * @return
	 */
	public static Set<BasicPath> reset()
	{
		Set<BasicPath> bps = new HashSet<BasicPath>();
		synchronized (entryBlocks)
		{
			for(String enteredMethod : enteredMethodsList)
				entryBlocks.get(enteredMethod).reset(enteredMethod, bpCache, bps);
			enteredMethodsList.clear();
		}
		return bps;
	}
	
	/**
	 * Clear all TrieSensor objects. Note that instrumented methods that are still executing will
	 * still have a reference to a stale TrieSensor objects, this should be garbage collected when those
	 * methods return.
	 * Any ticks observed through stale TrieSensors will be unrecoverable.
	 */
	public static void clear() 
	{ 
		reset();
	}
	
	public static void hard_reset() 
	{ 
		synchronized (entryBlocks)
		{
			entryBlocks.clear();
			enteredMethodsList.clear();
			bpCache.clear();
		}
	}
	
	public static final class ObservedBlock implements Comparable<Integer>
	{
		private static final ObservedBlock _FREE = new ObservedBlock(-1 << 1, null);
		
		//lowest bit is 'tick' and can change value
		//next lower 16 bits contain id and does not change value
		//upper 15 bits are always 0. 
		private int idt; 
		
		private final ObservedBlock parent;
		
		private ObservedBlock c1; //null if backedge
		private ObservedBlock c2;
		
		
		/* Most ObservedBlocks will have 0, 1 or 2 children.
		 * Only switch statements can cause more than 2 children
		 * Common case: children is null and only c1 and c2 are used.
		 * 
		 * Else: c1 and c2 are the first ticked children
		 * Only additional children are added to the ArrayList
		 */

		private ArrayList<ObservedBlock> children;
		
		private ObservedBlock(int i, ObservedBlock p) {
			idt = i;
			parent = p;
			c1 = c2 = _FREE;
		}
		
		//Special instance for back edges
		private ObservedBlock(final ObservedBlock actual_parent, final ObservedBlock cycle_head,
				final int idt)
		{
			this.parent = actual_parent;
			this.idt = idt;
			c1 = null;
			c2 = cycle_head;
		}
		
		
		@Override
		public int compareTo(Integer o)
		{
			//return 0 if equal
			//return pos number if this id > argument id
			//return neg number if this id < argument id
			
			//argument is id sans tick, shift field left by 2 to remove flag bits and get actual id.
			return (idt >>> 1) - o.intValue();
		}
		
		private ObservedBlock tick() 
		{
			if((idt&1)==0)
				this.idt++;
			if(c1==null)
				return c2;
			else
				return this;
		}
		
		private synchronized boolean tickIfUnticked() 
		{
			if((idt&1)==0) 
			{
				this.idt++;
				return true;
			} else
				return false;
		}
		
		//This method is never called on a backedge
		public synchronized ObservedBlock tick(final int i)
		{
			if((c1.idt >>> 1)==i) {
				return c1.tick();
			} else if((c2.idt >>> 1)==i) {
				return c2.tick();
			} else if(c1==_FREE) {
				return (c1 = extend(i)).tick();
			} else if(c2==_FREE) {
				return (c2 = extend(i)).tick();
			} else if(children==null) {
				(children = new ArrayList<ObservedBlock>(5)).add(extend(i));
				return children.get(0).tick();
			} else { //children != null
				int index = Collections.binarySearch(children, i);
				if(index<0) 
				{
					index = -index - 1;//remember binary search semantics...
					children.add(index,extend(i));
				}
				return children.get(index).tick();
			}				
		}
			
		//Returns new backedge to the first parent with this id or else a new Entry(id, this)
		//Precondition: All ancestors have their tick bit set.
		private ObservedBlock extend(int id)
		{
			id = (id << 1) + 1;
			ObservedBlock e = this;
			while(e.idt!=id)
				if( null == (e = e.parent))
					//parent is null, i.e. already reached upper parent. Return new Entry.
					return new ObservedBlock(id, this);
			//Found a parent with this id, return new backedge. It is possible that e==this.
			return new ObservedBlock(this, e, id);
		}
		
		private synchronized boolean reset(final String methodName, 
				final IdentityHashMap<ObservedBlock, BasicPath> cache,
				final Set<BasicPath> coverageSet)
		{
			/* If this node is not ticked, none of it's children can be ticked.
			 * Unless some stray concurrent method call from a previous test ticked them,
			 * after the TrieSensor was reset.
			 * For now: ignore this possibility.
			 * 
			 * Note: _FREE will always return false
			 */
			if((idt&1)==0)
				return false;
			
			//Reset tick bit.
			idt--;//Only works if tick bit was set, otherwise use alternative below:
			//id = id & ~1; //~1 = inverse of 1, all bits set except lowest
			
			//OK, this node was ticked.
			//Three cases: this is a (1) backedge, (2) terminal node, or (3) normal node
			//Normal node: at least one child must exist and be ticked.
			
			
			if(c1!=null) //exclude backedges
			{
				boolean notTerminal =   c1.reset(methodName, cache, coverageSet)
									  | c2.reset(methodName, cache, coverageSet);
				if(children!=null) {
					 for(ObservedBlock child : children)
						 notTerminal |= child.reset(methodName, cache, coverageSet);
				}
				if(notTerminal) //Not a terminal, don't add to coverage set
					return true;
			}
			
			//ticked terminal or backedge, add to coverage set
			
			BasicPath bp = cache.get(this);
			if(bp==null)
			{
				bp = BasicPath.create(methodName, 
						c1==null  ? parent.elem_cycle(c2, 2) //cycle
							: this.simple_path(1)            //simple path
				);
				cache.put(this, bp);
			}
			coverageSet.add(bp);
			return true;      
		}
		
		//call with length=1 on self
		private int[] simple_path(final int length) {
			final int[] ret = parent==null ? new int[length] : parent.simple_path(length+1);
			ret[ret.length-length] = (idt >>> 1);
			return ret;
		}
		
		//call with length=2 on actual parent of backedge: parent.elem_cycle(c2,2) where this=backedge
		private int[] elem_cycle(final ObservedBlock head, final int length)
		{
			if(head==this) {
				final int[] ret = new int[length];
				ret[ret.length-1] = ret[0] = (idt >>> 1);
				return ret;
			} else 
			{
				final int[] ret = parent.elem_cycle(head, length+1);
				ret[ret.length-length] = (idt >>> 1);
				return ret;
			}
		}
			
	}
	
	
	
	/*
	public static final class ObservedBlock
	{
		private final int id;
		private final ObservedBlock parent;

//		private final Map<Integer,ObservedBlock> possibleChildren;
//		private final Set<Integer> tickedChildren;
		
		
		//largest possible node id is 65535, we need to fill with an int larger than that
		//to maintain the sorted order of possChIndex and without accidentally putting in a real id.
		private static final int idFillValue = 65536;
		private int[] possChIndex;
		private ObservedBlock[] possChid;
		private BitSet tickedCh;
		
		private final Map<ObservedBlock,BasicPath> bps; //cached BasicPaths
		
		private int[] path(int length) {
			int[] ret = parent==null ? new int[length] : parent.path(length+1);
			ret[ret.length-length] = id;
			return ret;
		}
		
		private BasicPath bp(String methodName, ObservedBlock endNode)
		{
			BasicPath bp = bps.get(endNode);
			if(bp==null) 
			{
				if(endNode==this)
					bp = new BasicPath(methodName,path(1));
				else 
				{
					int[] path = path(2);
					path[path.length-1] = endNode.id;
					bp = new BasicPath(methodName,path);
				}
				bps.put(endNode, bp);
			}
			return bp;
		}
		
		private int indexOfChild(int nodeId)
		{
			int index = Arrays.binarySearch(possChIndex, nodeId);
			//if(index>=0) -> child already exists at this index
			if(index<0) //add child
			{
				index = 1 - index;
				growAndShiftIfNeeded(index);
				possChIndex[index] = nodeId;
				possChid[index] = parentOrNew(nodeId);
			}
			return index;	
		}
		
		private void growAndShiftIfNeeded(int index)
		{
			int len = possChid.length;
			if(possChid[len-1]!=null)
			{
    			int newLength = len << 1;
    			possChIndex = Arrays.copyOf(possChIndex, newLength);
    			Arrays.fill(possChIndex, len, newLength, idFillValue);
    			possChid = Arrays.copyOf(possChid, newLength);
			}
			if(possChid[index]!=null)
			{
				while(possChid[--len]==null) {}
				//len now contains the index of the last occupied slot
				
				int freeSlot = len+1;
				while(freeSlot>index)
				{
    				possChid[freeSlot] = possChid[len];
    				possChIndex[freeSlot] = possChIndex[len];
    				tickedCh.set(freeSlot, tickedCh.get(len));
    				freeSlot--; 
    				len--;
				}
				tickedCh.clear(index);
			}
		}
		
		
		private ObservedBlock(final int id, final ObservedBlock parent)
		{
			this.id = id;
			this.parent = parent;
//			possibleChildren = new HashMap<Integer, ObservedBlock>();
//			tickedChildren = new HashSet<Integer>();
			
			this.possChid = new ObservedBlock[3];
			this.possChIndex = new int[3];
			bps = new IdentityHashMap<ObservedBlock, BasicPath>(9);
			this.tickedCh = new BitSet(9);
		}
			
		public synchronized ObservedBlock tick(int i)
		{
			i = indexOfChild(i);
			tickedCh.set(i);
			return possChid[i];
		}
		
		synchronized ObservedBlock child(int i)
		{
			return possChid[indexOfChild(i)];
		}
		
		//Returns the first parent with this id or else a new Entry(id, this)
		private ObservedBlock parentOrNew(final int id)
		{
			ObservedBlock e = this;
			while(e.id!=id)
				if( null == (e = e.parent))
					//parent is null, i.e. already reached upper parent. Return new Entry.
					return new ObservedBlock(id, this);
			//Found a parent with this id, return it. It is possible that e==this.
			return e;
		}
				
		private synchronized void reset(Set<BasicPath> bps, final String methodName) 
		{
			if(tickedCh.isEmpty())
			{
				//terminal block
				bps.add(bp(methodName, this));
			}
			else
			{
				for(int i=tickedCh.nextSetBit(0); i>=0; i=tickedCh.nextSetBit(i+1)) 
				{
					if(possChid[i].parent==this)
						//traverse normal child
						possChid[i].reset(bps, methodName);
					else 
						//back edge, part of cycle: end path with back edge, don't traverse
						bps.add(bp(methodName,possChid[i]));
				}
				tickedCh.clear();				
			}	
		}
	}
	*/
}