package org.musicontroller.core;
   
   import java.util.Collection;
   import java.util.LinkedList;
   import java.util.List;
   import java.util.Set;
   import java.util.TreeSet;
   
   /**
   * A Keyword is a namable property of a Song. Keywords are hierarchical objects.
   * Their ordering is lexicographical after their name. The keyword names are case insensitive.
   * @author Varienaja
   */
  public class Keyword extends LinkableAbs implements Comparable<Keyword> {
  	private Keyword _parent;
  	private Set<Keyword> _children;
  	
  	// The maximal similarity between keywords. 
  	public static final int _maxSimilarityPower = 7;
  	public static final int _maxSimilarity = 1<<_maxSimilarityPower;
  	
  	public Keyword() {
  		_parent = null;
  		_children = null;
  	}
  	
  	/**
  	 * Factory method constructs a keyword with the given
  	 * name and a null parent.
  	 * @param name
  	 * @return The Keyword
  	 */
  	public static Keyword construct(String name) {
  		Keyword me = new Keyword();
  		me.setName(name);
  		return me;
  	}
  
  	/**
  	 * Factory method constructs a keyword with the given
  	 * name and parent.
  	 * @param name
  	 * @return The Keyword
  	 */
  	public static Keyword construct(String name, Keyword parent) {
  		Keyword me = new Keyword();
  		me.setName(name);
  		try {
  			me.setParent(parent);
  		} catch (KeywordCycleException e) {
  			// This is impossible: me is a freshly generated keyword and cannot be a parent of the parent.
  		}
  		return me;
  	}
  
  	public Keyword getParent() {
  		return _parent;
  	}
  	
  	public void setParent(Keyword parent) throws KeywordCycleException {
  		if(parent!=null && parent.isChildOf(this)) {
  			throw new KeywordCycleException();
  		}
  		this._parent = parent;
  	}
  	
  	/**
  	 * Determines if this keyword is a child of another
  	 * keyword. Used to prevent cyclic parent relationships.
  	 * 
  	 * @param other The other keyword.
  	 * @return True if this keyword is a child of the other keyword, or false otherwise.
  	 */
  	public boolean isChildOf(Keyword other) {
  		if(other==null) {
  			return false;
  		}
  		if(this.equals(other)) {
  			return false;
  		}
  		if(this.getParent()==null) {
  			return false;
  		}
  		if(this.getParent().equals(other)) {
  			return true;
  		}
  		return this.getParent().isChildOf(other);
  	}
  	
  	/**
  	 * Define Keyword business equality. Two keywords are equal
  	 * is there names are equal (disregarding case) and their parents are equal.
  	 */
  	@Override
  	public boolean equals(Object obj) {
  		if (this==obj) {
  			return true;
  		}
  		if (obj instanceof Keyword) {
 			Keyword other = (Keyword) obj;
 			boolean result = this.getName().equalsIgnoreCase(other.getName()) && 
 			    (
 			    		(this.getParent()==null && other.getParent()==null)
 			    	||	(this.getParent() != null && (this.getParent().equals(other.getParent())))
 			    );
 			return result;
 		} else {
 			return false;
 		}
 	}
 	
 	@Override
 	public int hashCode() {
 		int result = 0;
 		if(getName()!=null) {
 			result += getName().toLowerCase().hashCode();
 		}
 		if(getParent()!=null) {
 			result = (17 * result) + getParent().hashCode();
 		}
 		return result;
 	}
 	
 	/**
 	 * A short human readable representation of the keyword.
 	 */
 	public String toString() {
 		return this.getName();
 	}
 	
 	/**
 	 * Calculates similarity between keywords. The more parents the two keywords have in common,
 	 * the more similar they are. The similarity is defined as the length of the common chain
 	 * of parents the keyword share.
 	 * <ul>
 	 * <li>Equal keywords are maximally similar.
 	 * <li>Keywords without a common parent are not similar at all.
 	 * <li>Generalisation: Every step from keyword to its parent needed to arrive at a common
 	 *  ancestor reduces the similarity.
 	 * <li>Specialisation: The keyword is a parent of the keyword it is compared with.
 	 * <li>The length of the chain of common ancestors is not relevant.
 	 * </ul>
 	 * @param keyword The Keyword to compare this one to. This may not be NULL (will throw NullPointerException).
 	 * @return The amount of similar parents.
 	 */
 	public int similarityScore(Keyword keyword,StringBuilder sbout) {
 		if(this.equals(keyword)) {
 			return 1<<_maxSimilarityPower ;
 		} else {
 			boolean commonAncestorFound = false;
 			List<Keyword> myLineage = calcLineage();
 			List<Keyword> othersLineage = keyword.calcLineage();
 			StringBuilder sb = new StringBuilder();			
 			sb.append("<");
 			sb.append("kw1:");
 			sb.append(myLineage.toString());
 			sb.append(",kw2:");
 			sb.append(othersLineage.toString());
 			int generalisations = 0;
 			int specialisations = 0;
 			for (Keyword p1 : myLineage) {
 				// Check if the other keyword is a specialisation of myself. 
 				specialisations = 0;
 				for (Keyword p2 : othersLineage) {
 					if (p1.equals(p2)) {
 						commonAncestorFound = true;
 					}
 					if(commonAncestorFound) {
 						break;
 					}
 					specialisations++;
 				}
 				if(commonAncestorFound) {
 					break;
 				}
 				// The other keyword can only be a specialization of a generalisation of myself.
 				// Reduce the similarity.
 				generalisations++;
 			}
 			if(commonAncestorFound) {
 				sb.append(".G:");
 				sb.append(generalisations);
 				sb.append(",S:");
 				sb.append(specialisations);
 				sb.append("->");
 				sb.append((1 << (_maxSimilarityPower - generalisations)) - specialisations);
 				sb.append(">");
 				sbout.append(sb.toString());
 			}
 			int similarity = calculateSimilarity(commonAncestorFound,generalisations,specialisations);
 			return similarity;
 		}
 	}
 
 	/**
 	 * calculate the similarity score based on the number of generalisations needed to
 	 * get from one keyword to another. 
 	 * 
 	 * @param commonAncestorFound True if the compared keyword have a shared ancestor.
 	 * @param generalisations The number of generalisations.
 	 * @param specialisations The number of specialisations.
 	 * @return The calculated keyword similarity.
 	 */
 	public static int calculateSimilarity(boolean commonAncestorFound, int generalisations, int specialisations) {
 		if(!commonAncestorFound) {
 			return 0;
 		}
 		int remainingSimilarityPower = _maxSimilarityPower - generalisations;
 		int specialisationPenalty = 0;
 		if(remainingSimilarityPower<1) {
 			specialisationPenalty = 1;
 		} else {
 			specialisationPenalty = (1<< (remainingSimilarityPower-1));
 		}
 		if(remainingSimilarityPower<0) {
 			remainingSimilarityPower = 0;
 		}
 		return (1 << remainingSimilarityPower) - (specialisationPenalty * specialisations);
 	}
 
 	/**
 	 * Lists the entire path of parents of this keyword. The path ends iff:
 	 * <ul>
 	 * <li> The parent is NULL.
 	 * <li> The parent is equal to the keyword.
 	 * </ul>
 	 * @return A List containing this, parent-Keyword, grandparent-Keyword, etc.
 	 */
 	private List<Keyword> calcLineage() {
 		List<Keyword> l = new LinkedList<Keyword>();
 		l.add(this);
 		
 		Keyword p = getParent();
 		while ((p!=null) && (this!=p)) {
 			l.add(p);
 			p = p.getParent();
 		}
 		
 		return l;
 	}
 
 	public String getType() {
 		return "K";
 	}
 	
 	/**
 	 * The (non-persistent) Children of this Keyword.
 	 * @return This Keywords' child-keywords.
 	 */
 	public Set<Keyword> getChildren() {
 		return _children;
 	}
 	
 	/**
 	 * Adds a Keyword as a Child of this Keyword. The Childs parent must already
 	 * be set to this Keyword. The Children-property of a Keyword is 
 	 * non-persistent, and therefore uninitialized after reading a Keyword from
 	 * persistent storage.
 	 * @param keyword The (non-null) Child.
 	 * @return Whether addition to the Children was successful.
 	 */
 	public boolean addChild(Keyword keyword) {
 		if (keyword==null) return false; //No rubbish.
 		if (!keyword._parent.equals(this)) return false;
 		
 		if (_children == null) {
 			_children = new TreeSet<Keyword>();
 		}
 		return _children.add(keyword);
 	}
 	
 	/**
 	 * Constructs a Set of Keywords which are all topmost Keywords in the 
 	 * hierarchical Keyword-ordering. The Keywords in the resulting Set all
 	 * have their non-persistent children-properties initialized. The returned
 	 * set is in lexicographical order.
 	 * @param keywords All Keywords.
 	 * @return The Set of topmost Keywords.
 	 */
 	public static Set<Keyword> constructHierarchy(Collection<Keyword> keywords) {
 		Set<Keyword> result = new TreeSet<Keyword>();
 		
 		//Iterate through all Keywords. Keywords without a Parent are topmost.
 		//Every other Keyword is someones Child. We will first insert its
 		//topmost parent into the resultset, and then insert the Child at the
 		//correct position.
 		for (Keyword keyword : keywords) {
 			if (keyword.getParent()==null) {
 				result.add(keyword);
 			} else {
 				keyword.getParent().addChild(keyword);
 			}
 		}
 		
 		return result;
 	}
 	
 
 	/**
 	 * Returns the amount of children (including grandchildren, etc) of this
 	 * parent. The Hierarchy of the Keywords must have been constructed,
 	 * otherwise the result of this method will be 0.
 	 * @return The amount of Children.
 	 */
 	public int getChildCount() {
 		if (_children==null) return 0;
 		
 		int sum = 0;
 		for (Keyword child : _children) {
 			sum += 1 + child.getChildCount();
 		}
 		return sum;
 	}
 
 	/*
 	 * (non-Javadoc)
 	 * @see java.lang.Comparable#compareTo(java.lang.Object)
 	 */
 	public int compareTo(Keyword other) {
 		return getName().toLowerCase().compareTo(other.getName().toLowerCase());
 	}
 
 }