import java.util.*;

class Tree 
{
	/* counter to go through each token in query */
	public static int index = 0;
	/* list of all valid binary operations that are supported */
	public static String[] ops = {"WHERE", "TIMES", "SINCE", "UNTIL", "UNION", "MINUS", "JOIN", "SINCEJOIN", "UNTILJOIN"};
	/* list of all valid modal operations that are supported */
	public static String[] modalOps = {"PAST", "PREVIOUS", "ALWAYSPAST", "FUTURE", "NEXT", "ALWAYSFUTURE"};
	/* list of all conditional operators that are supported */
	public static String[] conds = {"AND", "OR"};
	/* list of all other operators or symbols that are supported */
	public static String[] otherOps = {"RENAME", "AS", "ON", "WITH", "{", "}", "COALESCE", "AT"};  // brackets!?! "(", ")"

	public static boolean renameFlag = false;
	public static boolean onWithFlag = false;
	
	public static int brackets = 0; /* counts the number of brackets and helps to build subtrees (subqueries) */

	public static void setConstants()
	{
		index=0;
		brackets=0;
		renameFlag = false;
		onWithFlag = false;
	}

	public static int getNoBracks()
	{
		return brackets;
	}

	public static TreeNode buildTree(String[] tokens, boolean subtree)
	{
		RootNode root = new RootNode (null);
		if (tokens[index].equals("("))
		{
			index++;
			brackets++;
		}
		root.setNext( build(tokens, subtree) );
		return root.getNext();
	}

	public static TreeNode build(String[] tokens, boolean subtree)
	{
		/* the root of the tree to be returned */
		RootNode root = new RootNode (null);
		/* flag to indicate when to stop building if constructing a subtree */ 
		boolean stop=false;

		/* go through all tokens or stop if end of building a subtree */
		while(index<tokens.length && !stop)
		{
			//System.out.println("wholeSubTree = "+subtree);
			/* check for a binary token */
			int type = evalToken(ops, tokens[index].toUpperCase());

			if (type!=99) /* the token is a valid binary operator */
			{
				BinaryNode b = new BinaryNode(ops[type], null, null);
				
				/* the tree constructed so far is set to the left of the operator */
				try
				{
					b.setLeftTree(root.getNext());
				}
				catch (NullPointerException e)
				{
					/* do nothing, root is pointing to null */
				}
				index++;
				
				if (ops[type].equals("WHERE")) /* A WHERE token */
				{
					/* build a CONSTRAINT subtree and set to the right of the WHERE operator */
					try
					{
						b.setRightTree(buildConstraint(tokens, subtree));//false));
					}
					catch (NullPointerException e)
					{
						/* do nothing, subtree returned is null */
					}
				}
				else
				{
					/* build a subtree and set to the right of the operator */
					try
					{
						b.setRightTree(build(tokens, subtree));//true));
					}
					catch (NullPointerException e)
					{
						/* do nothing, subtree returned is null */
					}
				}

				/* set the root to point to the new operator */
				root.setNext(b);
			}

			/***********************************************************************************/
			else if ( evalToken(modalOps, tokens[index].toUpperCase())!=99 ) // MODAL operators
			{
				/* create a modal node and assign corresponding modal operator entered by user */
				ModalNode mod = new ModalNode(tokens[index].toUpperCase(), null);

				/* the tree constructed so far is set to next, below the node */
				try
				{
					mod.setNext(root.getNext());
				}
				catch (NullPointerException e)
				{
					/* do nothing, root is pointing to null */
				}
				root.setNext(mod);
				index++;
			}

			else if (tokens[index].toUpperCase().equals("AT")) // 'AT time' operation
			{
				Integer maxTime = new Integer( UserInterface.getMaxTime() );
				String time = maxTime.toString();

				try
				{
					index++;		
					// check that a time argument has been supplied
					boolean valid = CheckToken(tokens[index]);
					if (valid)
					{
						CatchErr.tokenErr(tokens[index], "AT time_value");
						System.out.println("ASSUMPTION MADE: Using system max time value for AT operator");
					}
					else
						time = tokens[index];


				}
				catch (ArrayIndexOutOfBoundsException e)
				{
					CatchErr.missErr("a time", "AT");
					System.out.println("ASSUMPTION MADE: Using system max time value for AT operator");
				}
				
				
				/* create a AtTime node and assign the time value entered by user */
				AtTimeNode at = new AtTimeNode(time, null);

				/* the tree constructed so far is set to next, below the node */
				try
				{
					at.setNext(root.getNext());
				}
				catch (NullPointerException e)
				{
					/* do nothing, root is pointing to null */
				}
				root.setNext(at);
				index++;
			}
			/***********************************************************************************/
			///////////////////////////
			else if (tokens[index].toUpperCase().equals("RENAME"))
			{
				//if(!renameFlag)
				//{
				//	renameFlag=true;
				//	stop=true;
				//}

				//else
				//{

					index++;
					String[] oldFields = getRenameArgs(tokens, true, "AS");
					index++;
					String[] newFields = getRenameArgs(tokens, false, "AS");

					/* create a project node and assign with the list of fields to project */
					RenameNode rename = new RenameNode(oldFields, newFields, null);

					
					/* the tree constructed so far is set to next, below the node */
					try
					{
						rename.setNext(root.getNext());
					}
					catch (NullPointerException e)
					{
						/* do nothing, root is pointing to null */
					}
					root.setNext(rename);
				
					renameFlag=false;
				//}

			}
			///////////////////////////

			///////////////////////////
			else if (tokens[index].toUpperCase().equals("ON"))
			{
				if(!onWithFlag)
				{
					onWithFlag=true;
					stop=true;
				}

				else 
				{
					index++;
					String[] tabAFields = getRenameArgs(tokens, true, "WITH");
					index++;
					String[] tabBFields = getRenameArgs(tokens, false, "WITH");

					/* create a project node and assign with the list of fields to project */
					OnWithNode onWith = new OnWithNode(tabAFields, tabBFields, null);

					
					/* the tree constructed so far is set to next, below the node */
					try
					{
						onWith.setNext(root.getNext());
					}
					catch (NullPointerException e)
					{
						/* do nothing, root is pointing to null */
					}
					root.setNext(onWith);

					onWithFlag=false;
				}

			}
			///////////////////////////

			/* an open bracket */
			else if (tokens[index].equals("(")) 
			{
				index++; // ignore token
				brackets++;
				//////////////////////////////////
				try
				{
					TreeNode soFar = root.getNext();
					//stop=true;
					
				}
				catch (NullPointerException e)
				{
					root.setNext( build(tokens, subtree) );
				}
				//root.setNext( build(tokens, subtree) );
				//////////////////////////////////
			}

			/* a close bracket */
			else if (tokens[index].equals(")")) 
			{
				//if(subtree)
				//{
				//	stop=true; /* stop building the subtree */
				//}

				//////////////////////
				brackets--;
				stop=true;
				/////////////////////
				index++;
			}
				
			/* a project node */
			else if (tokens[index].equals("{"))
			{
				index++;

				/* get the fields names to project */
				String[] fields=projNames(tokens);

				/* create a project node and assign with the list of fields to project */
				ProjNode proj = new ProjNode(fields, null);

				/* the tree constructed so far is set to next, below the node */
				try
				{
					proj.setNext(root.getNext());
				}
				catch (NullPointerException e)
				{
					/* do nothing, root is pointing to null */
				}
				root.setNext(proj);
				index++;
			}

			/* a coalesce node */
			else if (tokens[index].toUpperCase().equals("COALESCE"))
			{
				/* create a coalesce node and place at top of tree */
				CoalesceNode coal = new CoalesceNode(null);

				/* the tree constructed so far is set to next, below the node */
				try
				{
					coal.setNext(root.getNext());
				}
				catch (NullPointerException e)
				{
					/* do nothing, root is pointing to null */
				}
				/* set root to point to the coalesce node */
				root.setNext(coal);
				index++;
			}

			/* assume that token is a variable name and corresponds to a table */
			else 
			{
				/* create a table node and place at top of tree */
				TableNode tab = new TableNode(tokens[index], null);

				/* the tree constructed so far is set to next, below the node */
				try
				{
					tab.setNext(root.getNext());
				}
				catch (NullPointerException e)
				{
					/* do nothing, root is pointing to null */
				}
				/* set root to point to the table node */
				root.setNext(tab);
				index++;
			}

		} /* end of while loop */

		/* return the built tree from tokens */
		return root.getNext();

	} /* end of method */


	public static int evalToken(String[]ops, String s)
	{
		int val=99;
		boolean found=false;
		int i=0; /* counter */

		while(i<ops.length && !found)
		{
			if (s.equals(ops[i]))
			{
				val=i;
				found=true;
			}
			i++;
		}

		return val;
	}

	public static String[] projNames(String[] tokens)
	{
		ArrayList names = new ArrayList();

		try
		{
			/* get all field names to project */
			while(!(tokens[index].equals("}")) && index<tokens.length)
			{
				boolean valid = CheckToken(tokens[index]);
				if (valid)
				{
					CatchErr.tokenErr(tokens[index], "'{...}' - PROJECT");
					System.out.println("The token '"+tokens[index]+"' is neglected from PROJECT");
				}
				else
				{
					names.add(tokens[index]);
				}
			index++;
			}
		}
		catch (ArrayIndexOutOfBoundsException e)
		{
			CatchErr.missErr("'}'", "'{...}' - PROJECT");
		}
		
		/* convert dynamic ArrayList to an array of Strings */
		String[] fields = new String[names.size()];
		for (int i=0; i<names.size(); i++)
		{
			fields[i]=(String)names.get(i);
		}

		return fields;
	}



	public static TreeNode buildConstraint(String[] tokens, boolean subtree)
	{
		/* the root of the tree to be returned */
		RootNode root = new RootNode (null);
		/* flag to indicate when to stop building if constructing a subtree */
		boolean stop=false;

		while(index<tokens.length && !stop)
		{
			//System.out.println("consSubTree = "+subtree);
			int type = evalToken(conds, tokens[index].toUpperCase());

			if (type!=99) /* the token is a valid condition operator */
			{
				BinaryNode b = new BinaryNode(conds[type], null, null);
				
				/* the constraint tree constructed so far is set to the left of the conditional operator */
				try
				{
					b.setLeftTree(root.getNext());
				}
				catch (NullPointerException e)
				{
					/* do nothing, root is pointing to null */
				}
				index++;

				/* build a constraint subtree and set to the right of the conditional operator */
				try
				{
					b.setRightTree(buildConstraint(tokens, true));
				}
				catch (NullPointerException e)
				{
					/* do nothing, subtree returned is null */
				}

				/* set root to point to the new operator */
				root.setNext(b);
			}

			else if (tokens[index].equals("(")) /* an open bracket */
			{
				index++; /* ignore token */
				/////////////////////////
				subtree=true;
				brackets++;
				//////////////////////////////////
				//try
				//{
				//	TreeNode soFar = root.getNext();
				//	stop=true;
					
				//}
				//catch (NullPointerException e)
				//{
					root.setNext( buildConstraint(tokens, subtree) );
				//}
				//////////////////////////////////
			}

			else if (tokens[index].equals(")")) /* a close bracket */
			{
				//if(subtree)
				//{
				//	stop=true; /* stop building the subtree */
				//}

				//////////////////////
				//if (subtree)
				//{
					index++;
				//}
				brackets--;
				stop=true;
				/////////////////////
				//index++;
			}

//			else if( evalToken(ops, tokens[index].toUpperCase())!=99 
//				    || tokens[index].equals("{")
//				    || tokens[index].toUpperCase().equals("COALESCE") )
			else if( CheckToken(tokens[index])==true )
			{
				//System.out.println("Error: Invalid token "+tokens[index]+" in a conditional statement");
				// should place this test at checking condition tokens ???

				/* end building the constraint tree and return back to the generation
				 * of WHERE condition in 'build' method
				 */
				stop=true;
			}

			else /* assume that variable name corresponds to a condition */
			{
				/* create a CONDITION node and place at top of tree */
				CondNode con = new CondNode(null, null, null, null);
				con.setArg(tokens[index]); /* get field name */
				index++;
				con.setOp(tokens[index]); /* get comparison operator */
				index++;
				/********************************/
				String strarg = tokens[index];
				int strlen = strarg.length();
				String firstchar = strarg.substring(0, 1);
				String lastchar = strarg.substring(strlen-1, strlen);

				if (firstchar.equals("'")) /* a string arg */
				{
					if (lastchar.equals("'"))
					{
						con.setVal(strarg); /* get val for comparison */
						index++;
					}
					else
					{
						index++;
						boolean lastnxtstr = false;
						while (index<tokens.length && !lastnxtstr)
						{
							String nxtarg = tokens[index];
							int nxtlen = nxtarg.length();
							String lastnxtchar = nxtarg.substring(nxtlen-1, nxtlen);
							if (lastnxtchar.equals("'"))
							{
								lastnxtstr=true;
							}
							strarg=strarg.concat(" ");
							strarg=strarg.concat(nxtarg);
							index++;
						}
						con.setVal(strarg); /* get val for comparison */
					}
				}
				else 
				{
					con.setVal(strarg); /* get val for comparison */
					index++;
				}
				/********************************/
				//con.setVal(tokens[index]); /* get val for comparison */
				//index++;
				/* the constraint tree constructed so far is set to next, below the node */
				try
				{
					con.setNext(root.getNext());
				}
				catch (NullPointerException e)
				{
					/* do nothing, root is pointing to null */
				}
				
				/* set root to point to the condition node */
				root.setNext(con);		
			}

		} /* end of while loop */

		/* return the constraint tree built from the conditional tokens */
		return root.getNext();

	} /* end of method */

	public static String[] getRenameArgs(String[] tokens, boolean old, String stopStr)
	{
		ArrayList names = new ArrayList();

		if (old)
		{
			while ( index<tokens.length && !tokens[index].toUpperCase().equals(stopStr) )
			{
				/* check that token is not a valid operator token */
				boolean valid = CheckToken(tokens[index]);
				//System.out.println("valid="+valid);
				if (valid)
				{
					String errMethod = "";
					//type of error 
					if (stopStr.equals("AS"))
						errMethod="RENAME attributes";
					if (stopStr.equals("WITH"))
					{
						errMethod="ON...WITH...";
						System.out.println("ASSUMPTION MADE: Performing a natural/since/until join respectively");
					}

					CatchErr.tokenErr(tokens[index], errMethod);
				}
				/* assume token is a valid column name */
				else
				{
					names.add(tokens[index]);
				}
				index++;
			} /* while loop */
		}
		else
		{
			while ( index<tokens.length && CheckToken(tokens[index])==false  )
			{
				/* assume token is a valid replacement column name */
				names.add(tokens[index]);
				index++;
			}
		}

		/* convert dynamic ArrayList to an array of Strings */
		String[] fields = new String[names.size()];
		for (int i=0; i<names.size(); i++)
		{
			fields[i]=(String)names.get(i);
		}

		return fields;
	}


	/************************************************************/
	/*		Catching invalid tokens within specific ops			*/
	/************************************************************/
	private static boolean CheckToken(String currentToken)
	{
		boolean invalid = false;
		int opVal = 99;
		currentToken = currentToken.toUpperCase();
		//System.out.println("uppercase="+currentToken);
		
		// check for a binary operator token
		opVal = evalToken(ops, currentToken);
		if (opVal!=99)
			invalid=true;

		// check for a modal operator token
		if (invalid==false)
		{
			opVal = evalToken(modalOps, currentToken);
			if (opVal!=99)
				invalid=true;
		}

		// check for a condition operator token
		if (invalid==false)
		{
			opVal = evalToken(conds, currentToken);
			if (opVal!=99)
				invalid=true;
		}

		// check for a all other operators/symbols token
		if (invalid==false)
		{
			opVal = evalToken(otherOps, currentToken);
			if (opVal!=99)
				invalid=true;
		}

		return invalid;
	}


}
