package de.ugoe.cs.eventbench.models;

import java.io.Serializable;
import java.security.InvalidParameterException;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;

import de.ugoe.cs.eventbench.models.Trie.Edge;
import de.ugoe.cs.eventbench.models.Trie.TrieVertex;
import de.ugoe.cs.util.StringTools;
import edu.uci.ics.jung.graph.DelegateTree;
import edu.uci.ics.jung.graph.Tree;

/**
 * <p>
 * This class implements a node of a trie. Each node is associated with a symbol
 * and has a counter. The counter marks the number of occurences of the sequence
 * defined by the path from the root of the trie to this node.
 * </p>
 * 
 * @author Steffen Herbold
 * 
 * @param <T>
 *            Type of the symbols that are stored in the trie.
 * @see Trie
 */
class TrieNode<T> implements Serializable {

	/**
	 * <p>
	 * Id for object serialization.
	 * </p>
	 */
	private static final long serialVersionUID = 1L;

	/**
	 * <p>
	 * Counter for the number of occurences of the sequence.
	 * </p>
	 */
	private int count;

	/**
	 * <p>
	 * Symbol associated with the node.
	 * </p>
	 */
	private final T symbol;

	/**
	 * <p>
	 * Child nodes of this node. If the node is a leaf this collection is empty.
	 * </p>
	 */
	private Collection<TrieNode<T>> children;

	/**
	 * <p>
	 * Constructor. Creates a new TrieNode without a symbol associated.<br>
	 * <b>This constructor should only be used to create the root node of the
	 * trie!</b>
	 * </p>
	 */
	TrieNode() {
		this.symbol = null;
		count = 0;
		children = new LinkedList<TrieNode<T>>();
	}

	/**
	 * <p>
	 * Constructor. Creates a new TrieNode. The symbol must not be null.
	 * </p>
	 * 
	 * @param symbol
	 *            symbol associated with the trie node
	 */
	TrieNode(T symbol) {
		if (symbol == null) {
			throw new InvalidParameterException(
					"symbol must not be null. null is reserved for root node!");
		}
		this.symbol = symbol;
		count = 0;
		children = new LinkedList<TrieNode<T>>();
	}

	/**
	 * <p>
	 * Copy-Constructor. Creates a new TrieNode as copy of other. Other must not
	 * be null.
	 * </p>
	 * 
	 * @param other
	 */
	TrieNode(TrieNode<T> other) {
		if (other == null) {
			throw new InvalidParameterException("other must not be null");
		}
		symbol = other.symbol;
		count = other.count;
		children = new LinkedList<TrieNode<T>>();
		for (TrieNode<T> child : other.children) {
			children.add(new TrieNode<T>(child));
		}
	}

	/**
	 * <p>
	 * Adds a given subsequence to the trie and increases the counters
	 * accordingly.
	 * </p>
	 * 
	 * @param subsequence
	 *            subsequence whose counters are increased
	 * @see Trie#add(List)
	 */
	public void add(List<T> subsequence) {
		if (!subsequence.isEmpty()) {
			if (!symbol.equals(subsequence.get(0))) { // should be guaranteed by
														// the
														// recursion/TrieRoot!
				throw new AssertionError("Invalid trie operation!");
			}
			count++;
			subsequence.remove(0);
			if (!subsequence.isEmpty()) {
				T nextSymbol = subsequence.get(0);
				getChildCreate(nextSymbol).add(subsequence);
			}
		}
	}

	/**
	 * <p>
	 * Returns the symbol associated with the node.
	 * </p>
	 * 
	 * @return symbol associated with the node
	 */
	public T getSymbol() {
		return symbol;
	}

	/**
	 * <p>
	 * Returns the number of occurences of the sequence represented by the node.
	 * </p>
	 * 
	 * @return number of occurences of the sequence represented by the node
	 */
	public int getCount() {
		return count;
	}

	/**
	 * <p>
	 * Returns the child of the node associated with the given symbol or creates
	 * it if it does not exist yet.
	 * </p>
	 * 
	 * @param symbol
	 *            symbol whose node is required
	 * @return node associated with the symbol
	 * @see Trie#getChildCreate(Object)
	 */
	protected TrieNode<T> getChildCreate(T symbol) {
		TrieNode<T> node = getChild(symbol);
		if (node == null) {
			node = new TrieNode<T>(symbol);
			children.add(node);
		}
		return node;
	}

	/**
	 * <p>
	 * Returns the child of the node associated with the given symbol or null if
	 * it does not exist.
	 * </p>
	 * 
	 * @param symbol
	 *            symbol whose node is required
	 * @return node associated with the symbol; null if no such node exists
	 * @see Trie#getChild(Object)
	 */
	protected TrieNode<T> getChild(T symbol) {
		for (TrieNode<T> child : children) {
			if (child.getSymbol().equals(symbol)) {
				return child;
			}
		}
		return null;
	}

	/**
	 * <p>
	 * Returns all children of this node.
	 * </p>
	 * 
	 * @return children of this node
	 */
	protected Collection<TrieNode<T>> getChildren() {
		return children;
	}

	/**
	 * <p>
	 * Searches the sub-trie of this trie node for a given sequence and returns
	 * the node associated with the sequence or null if no such node is found.
	 * </p>
	 * 
	 * @param sequence
	 *            sequence that is searched for
	 * @return node associated with the sequence
	 * @see Trie#find(List)
	 */
	public TrieNode<T> find(List<T> subsequence) {
		TrieNode<T> result = null;
		if (subsequence.isEmpty()) {
			result = this;
		} else {
			TrieNode<T> node = getChild(subsequence.get(0));
			if (node != null) {
				subsequence.remove(0);
				result = node.find(subsequence);
			}
		}
		return result;
	}

	/**
	 * <p>
	 * Returns a collection of all symbols that follow a this node, i.e., the
	 * symbols associated with the children of this node.
	 * </p>
	 * 
	 * @return symbols follow this node
	 * @see TrieNode#getFollowingSymbols()
	 */
	public Collection<T> getFollowingSymbols() {
		Collection<T> followingSymbols = new LinkedList<T>();
		for (TrieNode<T> child : children) {
			followingSymbols.add(child.getSymbol());
		}
		return followingSymbols;
	}

	/**
	 * <p>
	 * The string representation of a node is {@code symbol.toString()#count}
	 * </p>
	 * 
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		String str = symbol.toString() + " #" + count;
		if (!children.isEmpty()) {
			str += StringTools.ENDLINE + children.toString();
		}
		return str;
	}

	/**
	 * <p>
	 * Generates a {@link Tree} represenation of the trie.
	 * </p>
	 * 
	 * @param parent
	 *            parent vertex in the generated tree
	 * @param graph
	 *            complete tree
	 */
	void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) {
		TrieVertex currentVertex;
		if (isRoot()) {
			currentVertex = new TrieVertex("root");
			graph.addVertex(currentVertex);
		} else {
			currentVertex = new TrieVertex(getSymbol().toString() + "#"
					+ getCount());
			graph.addChild(new Edge(), parent, currentVertex);
		}
		for (TrieNode<T> node : children) {
			node.getGraph(currentVertex, graph);
		}
	}

	/**
	 * <p>
	 * Appends the current node to the dot representation of the trie.
	 * </p>
	 * 
	 * @param stringBuilder
	 *            {@link StringBuilder} to which the dot representation is
	 *            appended
	 */
	void appendDotRepresentation(StringBuilder stringBuilder) {
		String thisSaneId;
		if (isRoot()) {
			thisSaneId = "root";
		} else {
			thisSaneId = symbol.toString().replace("\"", "\\\"")
					.replaceAll("[\r\n]", "")
					+ "#" + count;
		}
		stringBuilder.append(" " + hashCode() + " [label=\"" + thisSaneId
				+ "\"];" + StringTools.ENDLINE);
		for (TrieNode<T> childNode : children) {
			stringBuilder.append(" " + hashCode() + " -> "
					+ childNode.hashCode() + ";" + StringTools.ENDLINE);
		}
		for (TrieNode<T> childNode : children) {
			childNode.appendDotRepresentation(stringBuilder);
		}
	}

	/**
	 * <p>
	 * Checks if the node is a leaf.
	 * </p>
	 * 
	 * @return true if the node is a leaf, false otherwise.
	 */
	protected boolean isLeaf() {
		return children.isEmpty();
	}

	/**
	 * <p>
	 * Checks if the node is the root.
	 * </p>
	 * 
	 * @return true if the node is the root of the trie, false otherwise
	 */
	protected boolean isRoot() {
		return symbol == null;
	}

	/**
	 * <p>
	 * Recursive methods that collects all nodes that are ancestors of leafs and
	 * stores them in the set.
	 * </p>
	 * 
	 * @param ancestors
	 *            set of all ancestors of leafs
	 */
	protected void getLeafAncestors(List<TrieNode<T>> ancestors) {
		boolean isAncestor = false;
		for (TrieNode<T> child : children) {
			child.getLeafAncestors(ancestors);
			isAncestor |= child.isLeaf();
		}
		if (isAncestor) {
			ancestors.add(this);
		}
	}

	/**
	 * <p>
	 * Returns the number of descendants of this node that are leafs. This does
	 * not only include direct children of this node, but all leafs in the
	 * sub-trie with this node as root.
	 * </p>
	 * 
	 * @return number of leafs in this sub-trie
	 */
	protected int getNumLeafs() {
		int numLeafs = 0;
		for (TrieNode<T> child : children) {
			if (child.isLeaf()) {
				numLeafs++;
			} else {
				numLeafs += child.getNumLeafs();
			}
		}
		return numLeafs;
	}

	/**
	 * <p>
	 * Sets the {@link #count} of this node.
	 * </p>
	 * <p>
	 * This function should only be used sparingly and very carefully! The count
	 * is usually maintained automatically by the training procedures.
	 * </p>
	 * 
	 * @param count
	 *            new count
	 */
	protected void setCount(int count) {
		this.count = count;
	}

	/**
	 * <p>
	 * Two TrieNodes are defined as equal, if their {@link #count},
	 * {@link #symbol}, and {@link #children} are equal.
	 * </p>
	 * 
	 * @see java.lang.Object#equals(java.lang.Object)
	 */
	@SuppressWarnings("rawtypes")
	@Override
	public boolean equals(Object other) {
		if (other == this) {
			return true;
		}
		if (other instanceof TrieNode) {
			TrieNode otherNode = (TrieNode) other;
			if (symbol == null) {
				return count == otherNode.count && otherNode.symbol == null
						&& children.equals(otherNode.children);
			} else {
				return count == otherNode.count
						&& symbol.equals(((TrieNode) other).symbol)
						&& children.equals(((TrieNode) other).children);
			}
		}
		return false;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#hashCode()
	 */
	@Override
	public int hashCode() {
		int multiplier = 17;
		int hash = 42;
		if (symbol != null) {
			hash = multiplier * hash + symbol.hashCode();
		}
		hash = multiplier * hash + count;
		hash = multiplier * hash + children.hashCode();
		return hash;
	}
}