package org.musicontroller.songselection;
   
   import java.util.Date;
   import java.util.HashMap;
   import java.util.HashSet;
   import java.util.Iterator;
   import java.util.List;
   import java.util.Map;
   import java.util.Set;
  
  import org.apache.log4j.Logger;
  import org.musicontroller.core.Band;
  import org.musicontroller.core.Keyword;
  import org.musicontroller.core.Keywordbag;
  import org.musicontroller.core.Song;
  import org.musicontroller.dao.Dao;
  import org.musicontroller.security.IUser;
  import org.varienaja.util.DateTools;
  import org.varienaja.util.LRUMap;
  
  public class AdvancedRandomSongSelector implements SongSelector {
  	private static final Logger log = Logger.getLogger(AdvancedRandomSongSelector.class);
  
  	/**
  	 * A Map of Strings (kwbId1,kwbId2) --> Similarity score
  	 */
  	private static Map<String,Integer> SCORES = new LRUMap<String,Integer>("KeywordSimilarityScores",1000);
  	
  	private Dao _dao;
  
  	/**
  	 * A map, containing knowledge of the popularity of all Bands.
  	 */
  	private Map<Long,PlaySkipContainer> _bandPopularity;
  
  	/**
  	 * A map, containing knowledge of the popularity of all Keywords.
  	 */
  	private Map<Long,PlaySkipContainer> _keywordPopularity;
  
  	/**
  	 * The specific implementation of selecting the best song from a list of
  	 * candidates, using the advanced random algorithm.
  	 * @param candidates The list of candidates
  	 * @param user The user for who we're selecting
  	 * @param lpc The LastPlayedContainer
  	 * @return The Song from the candidatelist that fitted best.
  	 */
  	private Song selectSongInternal(List<Song> candidates, IUser user, LastPlayedContainer lpc) {
  		Set<Song> best = new HashSet<Song>();
  		Song bestsong = null;
  		int maxscore=Integer.MIN_VALUE;
  
  		// Stage 1: select highest scoring candidates
  		for (Song song : candidates) {
  			int score = calculateScore(song,lpc,user);
  			if (score>=maxscore) {
  				if (score>maxscore) { // New highscore: clear best-set
  					best.clear();
  					maxscore=score;
  				}
  				best.add(song);
  			}
  		}
  
  		// Stage 2: if there are more than one equally scoring songs, pick the
  		// best, based on the EventScore.
  		if (best.size()==1) {
  			bestsong = best.iterator().next();
  		} else {
  			maxscore=Integer.MIN_VALUE;
  			for (Song song : best) {
  				int songscore = calculateEventScore(user,song);
  				if (songscore>maxscore) {
  					maxscore = songscore; 
  					bestsong = song;
  				}
  			}
  		}
  		if (bestsong==null) {
  			return null;
  		}
  		if (log.isInfoEnabled()) {
  			Date lastYear = DateTools.lastYear();
  			log.info("Song selected: "+
  					bestsong.getBand().getName()+
  					" - "+bestsong.getName()+
  					" P:"+bestsong.getPlaycount(user,lastYear,null)+
  					" R:"+bestsong.getRequestcount(user,lastYear,null)+
  					" S:"+bestsong.getSkipcount(user,lastYear,null)
  			);
  		}
  
  		return bestsong;
  	}
  
  	/*
  	 * (non-Javadoc)
  	 * @see org.musicontroller.songselection.SongSelector#selectSong(java.util.List, org.musicontroller.songselection.LastPlayedContainer, org.musicontroller.security.IUser)
 	 */
 	public Song selectSong(List<Song> candidates, LastPlayedContainer lpc, IUser user) {
 		if(candidates==null) {
 			return null;
 		}
 		if(lpc==null) {
 			lpc = new LastPlayedContainer();
 		}
 		Song result = selectSongInternal(candidates,user,lpc);
 		return result;
 	}
 
 	/**
 	 * Calculates the score for a Song. The score is the sum of the playcount score, the
 	 * skip score, the request score, the keyword similarity score, the band popularity score,
 	 * and a possible penalty for songs by recently played bands.
 	 * <ul>
 	 * <li>The playcount score is the square root of the number of plays the song got in the last year.
 	 * <li>The skip score is the number of skip events of the song in the last year, times -1.
 	 * <li>The request score if the number of request events of the song in the last year.
 	 * <li>The keyword similarity score is TODO: explain this.
 	 * <li>The band popularity score is TODO: explain this.
 	 * <li>Songs played by bands that received a played event recently get a penalty equal to the
 	 * keyword similarity score.
 	 * </ul>
 	 */
 	private int calculateScore(Song song, LastPlayedContainer lpc,IUser user) {
 		StringBuilder sb = new StringBuilder();
 		int score=0;
 		sb.append(song.getBand().getName());
 		sb.append(" - ");
 		sb.append(song.getName());
 		sb.append(" ");
 
 		int playscore = calculateEventScore(user,song); 
 		score = playscore;
 		if(playscore!=0) {
 			sb.append("(play:");
 			sb.append(playscore);
 			sb.append(")");
 		}
 		
 		//The skips are already a part of the playscore, but because skips are
 		//such a clear indication of dislike, we penalize extra for them.
 		int skipscore = -1 * song.getSkipcount(user,DateTools.lastYear(),null);
 		score += skipscore;
 		if(skipscore!=0) {
 			sb.append("(skip:");
 			sb.append(skipscore);
 			sb.append(")");
 		}
 		
 		int kwscore = calculateKeywordScore(song, lpc, sb);
 		score += kwscore;
 		
 		int bandPenalty = getPenalty(song.getBand()); // score negative for often-skipped bands.
 		score += bandPenalty;
 		if(bandPenalty!=0) {
 			sb.append("(bandPenalty:");
 			sb.append(bandPenalty);
 			sb.append(")");
 		}
 
 		sb.append("[");
 		sb.append(score);
 		sb.append("]");
 		log.debug(sb.toString());
 		return score;
 	}
 
 	/**
 	 * calculates the song score for keyword similarity with recently played songs.
 	 * If the song is by the same band as one of the recently played songs, the song
 	 * cannot get a positive score (but negative scores still apply).
 	 * 
 	 * @param song The candidate song 
 	 * @param lpc The container of the set of recently played songs.
 	 * @param sb A string builder for receiving logging messages.
 	 * @return The keyword similarity score for this song compared to the recently played songs.
 	 */
 	private int calculateKeywordScore(Song song, LastPlayedContainer lpc, StringBuilder sb) {
 		int totalkwscore = 0;
 		Keywordbag songKeywords = song.getKeywordbag();
 		if(songKeywords!=null) {
 			// The last 3 songs weigh positive, one weighs 0, earlier played songs
 			// negative.
 			// The more recently a song is played, the more keyword-similarity
 			// counts in the score.
 			// This is reflected by the modifier.
 			int modifier=4-lpc.getSize(); 
 			Iterator<LastPlayedEntry> it = lpc.getIterator();
 			while (it.hasNext()) {
 				sb.append(" (");
 				sb.append(modifier);
 				sb.append(" * ");
 				LastPlayedEntry lastsongentry = it.next();
 	
 				Song lastsong = getDao().getSongById(lastsongentry.getSongid());
 				if (lastsong!=null) {
 					boolean scoreNegative = false;
 					
 					int kwscore = kwbSimilarityScore(songKeywords, lastsong.getKeywordbag(), sb);
 					//If the lastsong was skipped, or if the Band matches we let this one count negative:
 					if (kwscore>0) {
 						scoreNegative = (!lastsongentry.isPlayedEntirely() || song.getBand().equals(lastsong.getBand()));
 					}
 					sb.append(scoreNegative ? "!" : "");
 					sb.append(kwscore);
 					sb.append(scoreNegative ? "!" : "");
 					
 					// Use the modifier on the keyword score.
 					kwscore *= modifier;
 					if (scoreNegative && kwscore>0) {
 						totalkwscore -= kwscore;
 					} else {
 						totalkwscore += kwscore;
 					}
 				} else {
 					log.debug("Detected SongID in lastplayedcontainer for " +
 							"which there is no song in the database. Was is " +
 							"just deleted or merged? The id is: " + lastsongentry.getSongid());
 				}
 				sb.append(") ");
 				sb.append(it.hasNext() ? "+" : "= ");
 				modifier++;
 			}
 			sb.append(totalkwscore);
 			sb.append(" sqrt(sqrt(" + totalkwscore + ")) = ");
 			// Use the double square root as the final keyword score.
 			if(totalkwscore<0) {
 				totalkwscore = -1 * isqrt(isqrt(-1 * totalkwscore));
 			} else {
 				totalkwscore = isqrt(isqrt(totalkwscore));
 			}
 		}
 		sb.append(totalkwscore);
 		return totalkwscore;
 	}
 
 	/**
 	 * Return a score for the popularity of the song. The score is the square
 	 * root of the popularity. A popularity of 0 still earns the song 1 point
 	 * (there should be no difference between a 0 or 1 popularity score).
 	 * @param user The logged in user (for calculating the popularity).
 	 * @param song The song.
 	 * @return A score for the popularity of the song in the last year.
 	 */
 	private int calculateEventScore(IUser user, Song song) {
 		int nplays = song.getPopularity(user,DateTools.lastYear(),null);
 		int evScore = nplays == 0 ? 1 : nplays < 0 ? -1*isqrt(-1 * nplays) : isqrt(nplays);
 		return evScore;
 	}
 	
 	/**
 	 * Helper function for the <tt>isqrt</tt> method. 
 	 * @param n
 	 * @param i
 	 * @return
 	 */
 	private static int next(int n, int i) {
 		return (n + i/n) >> 1;
 	}
 
 	/**
 	 * Calculates the integer square root of an integer using Newtons' method.
 	 * This only works for numbers >= 0.
 	 * 
 	 * From: http://www.codecodex.com/wiki/index.php?title=Calculate_an_integer_square_root.
 	 * 
 	 * @param number The number to take the square root from.
 	 * @return The square root of the number.
 	 */
 	private static int isqrt(int number) {
 		if(number<0) {
 			throw new IllegalArgumentException("Cannot take the sqare root of a negative integer.");
 		}
 		int n  = 1;
 		int n1 = next(n, number);
 
 		while(Math.abs(n1 - n) > 1) {
 			n  = n1;
 			n1 = next(n, number);
 		}
 		while((n1*n1) > number) {
 			n1 -= 1;
 		}
 		return n1;
 	}
 
 
 	/**
 	 * Setter for the DAO.
 	 * 
 	 * @param dao
 	 *            The DAO.
 	 */
 	public void setDao(Dao dao) {
 		_dao = dao;
 	}
 
 	public Dao getDao() {
 		return _dao;
 	}
 
 	public AdvancedRandomSongSelector() {
 		_bandPopularity = new HashMap<Long,PlaySkipContainer>();
 		_keywordPopularity = new HashMap<Long,PlaySkipContainer>();
 	}
 
 	static class PlaySkipContainer {
 		private int _playcount;
 		private int _skipcount;
 
 		public PlaySkipContainer(int playcount,int skipcount) {
 			_playcount = playcount;
 			_skipcount = skipcount;
 		}
 
 		/**
 		 * Calculates the popularity-score for a skip/play-ratio. If something
 		 * has been skipped at least 3 times, it's popularity decreases. A score
 		 * can only be negative or 0.
 		 * 
 		 * @return A value <=0
 		 */
 		public int getPopularity() {
 			if (_skipcount<3) return 0;
 			if (_playcount>=_skipcount) return 0;
 			return _playcount-_skipcount;
 		}
 
 		public void addPlay() {
 			_playcount++;
 		}
 
 		public void addSkip() {
 			_skipcount++;
 		}
 
 		public String toString() {
 			return Integer.toString(getPopularity());
 		}
 	}
 
 	/**
 	 * Returns an integer, representing the penalty of a Band.
 	 * @param band The Band to check the popularity for.
 	 * @return An integer equal to or smaller than 0.
 	 */
 	public int getPenalty(Band band) {
 		PlaySkipContainer psc = _bandPopularity.get(band.getId());
 		if (psc==null) return 0;
 
 		return psc.getPopularity();
 	}
 
 	/**
 	 * Returns an integer, representing the penalty of a Keyword.
 	 * @param keyword The Keyword to check the popularity for.
 	 * @return An integer equal to or smaller than 0.
 	 */
 	public int getPenalty(Keyword keyword) {
 		PlaySkipContainer psc = _keywordPopularity.get(keyword.getId());
 		if (psc==null) return 0;
 
 		return psc.getPopularity();
 	}
 
 	/**
 	 * Adds knowledge about a Band. Knowledge is 'sparse', Bands without plays
 	 * and skips are not stored.
 	 * 
 	 * @param bandid
 	 *            The bandid
 	 * @param playcount
 	 *            The amount of plays for this band
 	 * @param skipcount
 	 *            The amount of skips for this band
 	 */
 	public void addBandKnowledge(Long bandid, int playcount, int skipcount) {
 		if (playcount>0 || skipcount>0) {
 			PlaySkipContainer psc = new PlaySkipContainer(playcount,skipcount);
 			_bandPopularity.put(bandid,psc);
 		}
 	}
 
 	/**
 	 * Adds knowledge about a Keyword. Knowledge is 'sparse', Keywords without
 	 * plays and skips are not stored.
 	 * 
 	 * @param keywordid
 	 *            The keywordid
 	 * @param playcount
 	 *            The amount of plays for this keyword
 	 * @param skipcount
 	 *            The amount of skips for this keyword
 	 */
 	public void addKeywordKnowledge(Long keywordid, int playcount, int skipcount) {
 		if (playcount>0 && skipcount>0) {
 			PlaySkipContainer psc = new PlaySkipContainer(playcount,skipcount);
 			_keywordPopularity.put(keywordid,psc);
 		}
 	}
 
 	/*
 	 * (non-Javadoc)
 	 * 
 	 * @see org.musicontroller.songselection.SongSelector#addBandPlay(long)
 	 */
 	public void addBandPlay(long bandid) {
 		PlaySkipContainer psc = _bandPopularity.get(bandid);
 		if (psc==null) {
 			psc = new PlaySkipContainer(1,0);
 			_bandPopularity.put(bandid,psc);
 		} else {
 			psc.addPlay();
 		}
 	}
 
 	/*
 	 * (non-Javadoc)
 	 * 
 	 * @see org.musicontroller.songselection.SongSelector#addBandSkip(long)
 	 */
 	public void addBandSkip(long bandid) {
 		PlaySkipContainer psc = _bandPopularity.get(bandid);
 		if (psc==null) {
 			psc = new PlaySkipContainer(0,1);
 			_bandPopularity.put(bandid,psc);
 		} else {
 			psc.addSkip();
 		}
 	}
 
 	/*
 	 * (non-Javadoc)
 	 * 
 	 * @see org.musicontroller.songselection.SongSelector#addKeywordPlay(long)
 	 */
 	public void addKeywordPlay(long keywordid) {
 		PlaySkipContainer psc = _keywordPopularity.get(keywordid);
 		if (psc==null) {
 			psc = new PlaySkipContainer(1,0);
 			_keywordPopularity.put(keywordid,psc);
 		} else {
 			psc.addPlay();
 		}
 	}
 
 	/*
 	 * (non-Javadoc)
 	 * 
 	 * @see org.musicontroller.songselection.SongSelector#addKeywordSkip(long)
 	 */
 	public void addKeywordSkip(long keywordid) {
 		PlaySkipContainer psc = _keywordPopularity.get(keywordid);
 		if (psc==null) {
 			psc = new PlaySkipContainer(0,1);
 			_keywordPopularity.put(keywordid,psc);
 		} else {
 			psc.addSkip();
 		}
 	}
 	
 	/**
 	 * Calculates the amount of similarity between two Keywordbags. This method
 	 * used a caching mechanism. Calculating a similarity between Keywordbags is
 	 * relatively expensive. Once such a score has been calculated, this method
 	 * is of O(1).
 	 * 
 	 * @param kwb1 The first keywordbag.
 	 * @param kwb2 The second keywordbag.
 	 * @param sb A StringBuffer to write debug-info to.
 	 * @return An integer, expressing the amount of similarity.
 	 */
 	private int kwbSimilarityScore(Keywordbag kwb1, Keywordbag kwb2, StringBuilder sb) {
 		//Create a key out of the two keywordbags and the user, making sure that x,y == y,x
 		StringBuilder hashkeyBuilder = new StringBuilder();
 		if(kwb1==null) {
 			if(kwb2==null) {
 				hashkeyBuilder.append("null,null");
 			} else {
 				hashkeyBuilder.append("null,");
 				hashkeyBuilder.append(kwb2.getId());
 			}
 		} else if (kwb2==null) {
 			hashkeyBuilder.append(kwb1.getId());
 			hashkeyBuilder.append(",null");
 		} else if (kwb1.getId()<kwb2.getId()) {
 			hashkeyBuilder.append(kwb1.getId());
 			hashkeyBuilder.append(",");
 			hashkeyBuilder.append(kwb2.getId());
 		} else {
 			hashkeyBuilder.append(kwb2.getId());
 			hashkeyBuilder.append(",");
 			hashkeyBuilder.append(kwb1.getId());			
 		}
 		String key = hashkeyBuilder.toString();
 		Integer score = SCORES.get(key);
 		
 		if (score!=null) {
 			return score;
 		}
 		
 		//If we manage to get here, we need to calculate a new score.
 		int kwscore = 0;
 		Set<Keyword> alreadyCounted = new HashSet<Keyword>();
 		int kwcounter = 0; //The amount of keywords of the song.
 		for (Keyword kw : kwb1.getKeywords()) {
 			kwcounter++;
 			if(alreadyCounted.contains(kw)) {
 				continue;
 			}
 			kwscore += getPenalty(kw); // score negative for often-skipped keywords.
 			if (kwb2!=null) {
 				for(Keyword kwlast : kwb2.getKeywords()) {
 					if(alreadyCounted.contains(kwlast)) {
 						continue;
 					}
 					int similarity = kw.similarityScore(kwlast,sb);
 					if(similarity>0) {
 						sb.append("(sim:");
 						sb.append(similarity);
 						sb.append(")");
 						while(kwlast.getParent()!=null && !kwlast.getParent().equals(kwlast)) {
 							Keyword parent = kwlast.getParent();
 							sb.append("(ac:");
 							sb.append(parent);
 							sb.append(")");
 							alreadyCounted.add(parent);
 							kwlast = kwlast.getParent();	
 						}
 					}
 					kwscore+=similarity;
 				}
 			}
 		}
 		
 		if (kwcounter>0) {
 			kwscore = kwscore / kwcounter;
 		}
 		
 		SCORES.put(key, kwscore);
 		return kwscore;
 	}
 	
 /*	
 */
 
 	
 }