package basics.collections.index;

import basics.testing.Test;

/**
 * This constructs an index as a forest, each node is realized as a hash map where the key stores only one sign.
 * @author ks
 */
public class HashedCharacterTree extends HashedCharacterTreeBase
{
	private static final int NOTFOUND = -1;
	
	class IHashNode extends HashNode<Integer>
	{
		boolean rmFlag = false;
		
		/**
		 * Element constructor
		 * @param c
		 * @param i
		 */
		IHashNode(int i)
		{
		   this.value = i;
		}
		
		/**
		 * Root constructor
		 */
		IHashNode()
		{
		   super();
		}
		
		boolean isMatch()
		{
		   return value != null && value > NOTFOUND;
		}
	}
	
	private IHashNode root = new IHashNode();
	
	HashNode<?> getRoot()
	{
	   return root;
	}
	
	int enshure(String term, int nextfree)
	{
	   return enshure(nextfree, root, term, 0, term.length(), NOTFOUND);
	}
	
	int enshure(int nextfree, IHashNode node, String T, int i, int x, int matchpos)
	{
	   //   if(i == x)
	   //      throw new Failure("HashTree does not support empty strings.");
	   int ipp = i + 1;
	   String c = T.substring(i, ipp);
	   IHashNode nextnode = null;
	   if(node.next == null)
	      node.createNext(); //new HashMap<String, IHashNode>();
	   else
	      nextnode = (IHashNode)node.next.get(c);
	   if(nextnode == null)
	   {
	      if(ipp == x)
	      {
	         nextnode = new IHashNode(nextfree);
	         node.next.put(c, nextnode);
	         return nextfree;
	      }
	      else
	      {
	         nextnode = new IHashNode(NOTFOUND);
	         node.next.put(c, nextnode);
	         return enshure(nextfree, nextnode, T, ipp, x, nextnode.value);
	      }
	   }
	   else
	   {
	      if(ipp == x)
	      {
	         //if removed earlier, overwrite: 
	         if(nextnode.rmFlag)
	         {
	            nextnode.value = nextfree;
	            nextnode.rmFlag = false;
	            node.next.put(c, nextnode);
	            return nextfree;
	         }
	         else
	         {
	            //term ends on transition node? then make it a leaf
	            if(nextnode.value == -1)
	               nextnode.value = nextfree;
	            return nextnode.value;
	         }
	      }
	      else
	      {
	         return enshure(nextfree, nextnode, T, ipp, x, nextnode.value);
	      }
	   }
	}
	
	/**
	 * Retrieve index number of a term. The index number applies to an external list position.
	 * @param term
	 * @return 0...n if found, or -1 if not found.
	 */
	int retrieve(String term)
	{
	   return retrieve(root, term, 0, term.length(), NOTFOUND);
	}
	
	private int retrieve(IHashNode currentNode, String term, int i, int termLen, int matchpos)
	{
	   IHashNode nextNode;
	   if(i == termLen)
	      return currentNode.rmFlag ? NOTFOUND : matchpos;
	   if(currentNode.next == null)
	      return NOTFOUND;
	   if((nextNode = (IHashNode)nextNode(term, i, termLen, currentNode)) == null)
	      return NOTFOUND;
	   return retrieve(nextNode, term, i + 1, termLen, nextNode.value);
	}
	
	void retrieveFuzzy(Collector results, HashNode<?> _node, String term, int i, int size,
	   int limit, int limit0, int r)
	{
	   IHashNode node = (IHashNode)_node;
	   int k;
	   IHashNode nextnode = null;
	   if(!deadNode(node))
	   {
	      if(matching(term, i, size, limit, node, r))
	         results.insertMatches(node.value, matchRatio(term, limit0, limit, size, r));
	      if(limit > 0)
	      {
	         if((nextnode = (IHashNode)nextNode(term, i, size, node)) != null)
	            retrieveFuzzy(results, nextnode, term, i + 1, size, limit, limit0, r + 1);
	         else
	            for(int tolerance = 0; tolerance < 2 * limit; tolerance++)
	               if((k = 1 + i + flipflop(tolerance)) >= 0)
	                  if(retrieveFuzzySet(results, node, term, k, size, limit - 1, limit0, r))
	                     ; // or break?
	      }
	   }
	}
	
	/**
	 * Remove a term, this only sets a flag.
	 * @param term to be removed from the index.
	 */
	void remove(String term)
	{
	   remove(root, term, 0, term.length());
	}
	
	private void remove(IHashNode cset, String T, int i, int x)
	{
	   if(i == x)
	      cset.rmFlag = true;
	   else
	   {
	      int ipp = i + 1;
	      if(cset.next != null)
	      {
	         IHashNode nextset = (IHashNode)cset.next.get(T.substring(i, ipp));
	         if(nextset != null)
	            remove(nextset, T, ipp, x);
	      }
	   }
	}
	
	public static void unittest()
	{
	   HashedCharacterTree ht = new HashedCharacterTree();
	   String a = "abcd";
	   String b = "xyz";
	   String c = "hallo";
	   String d = "hall";
	   ht.enshure(a, 0);
	   ht.enshure(b, 1);
	   ht.enshure(c, 2);
	   Test.assertTrue(ht.retrieve(a) == 0, a + " not located correctly at 0 but at " + ht.retrieve(a));
	   Test.assertTrue(ht.retrieve(b) == 1, b + " not located correctly at 1 but at " + ht.retrieve(b));
	   Test.assertTrue(ht.retrieve(c) == 2, c + " not located correctly at 2 but at " + ht.retrieve(c));
	   Test.assertTrue(ht.retrieve(c + "_") == -1, c + "_ was located, but should be there, pos "
	      + ht.retrieve(c + "_"));
	   Test.assertTrue(ht.retrieve(d) == -1, d + " was located, but should be there, pos "
	      + ht.retrieve(d));
	   ht.remove(b);
	   Test.assertTrue(ht.retrieve(b) == -1, b + " located after remove at " + ht.retrieve(b));
	   ht.enshure(b, 11);
	   Test.assertTrue(ht.retrieve(b) == 11, b
	      + " not located correctly after remove+enshure at 11 but at " + ht.retrieve(b));
	   Throwable e = null;
	   try
	   {
	      ht.enshure("", -100);
	   }
	   catch(Throwable e_)
	   {
	      e = e_;
	   }
	   Test.handleAsFeature(e, "Adding an empty string should have failed.");
	}
}