source: sample/hadoop-0.17/tw/org/nchc/util/ScoreSortedMap.java @ 20

/*
 * Cloud9: A MapReduce Library for Hadoop
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you
 * may not use this file except in compliance with the License. You may
 * obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0 
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
 * implied. See the License for the specific language governing
 * permissions and limitations under the License.
 */

package tw.org.nchc.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * A Map that holds scores (doubles) associated with each object (key) and
 * supports iteration by score. Many applications call for this type of
 * functionality: the ability to associate scores with objects coupled with the
 * ability to sort entries by their scores.
 * 
 * @param <K>
 *            type of key
 */
public class ScoreSortedMap<K extends Comparable<K>> extends HashMap<K, Double> {

  private static final long serialVersionUID = 2983410765L;

  /**
   * Constructs a <code>ScoreSortedMap</code>.
   */
  public ScoreSortedMap() {
    super();
  }

  /**
   * Returns the all entries sorted by scores.
   * 
   * @return a sorted set view of the entries sorted by scores
   */
  public SortedSet<Map.Entry<K, Double>> getSortedEntries() {
    SortedSet<Map.Entry<K, Double>> entries = new TreeSet<Map.Entry<K, Double>>(
        new Comparator<Map.Entry<K, Double>>() {
          public int compare(Map.Entry<K, Double> e1,
              Map.Entry<K, Double> e2) {
            if (e1.getValue() > e2.getValue()) {
              return -1;
            } else if (e1.getValue() < e2.getValue()) {
              return 1;
            }
            return e1.getKey().compareTo(e2.getKey());
          }
        });

    for (Map.Entry<K, Double> entry : this.entrySet()) {
      entries.add(entry);
    }

    return Collections.unmodifiableSortedSet(entries);
  }

  /**
   * Returns the <i>n</i> top entries sorted by scores.
   * 
   * @param n
   *            number of entries to retrieve
   * @return a Set view of the entries sorted by scores
   */
  public SortedSet<Map.Entry<K, Double>> getSortedEntries(int n) {

    SortedSet<Map.Entry<K, Double>> entries = new TreeSet<Map.Entry<K, Double>>(
        new Comparator<Map.Entry<K, Double>>() {
          public int compare(Map.Entry<K, Double> e1,
              Map.Entry<K, Double> e2) {
            if (e1.getValue() > e2.getValue()) {
              return -1;
            } else if (e1.getValue() < e2.getValue()) {
              return 1;
            }
            return e1.getKey().compareTo(e2.getKey());
          }
        });

    int cnt = 0;
    for (Map.Entry<K, Double> entry : getSortedEntries()) {
      entries.add(entry);
      cnt++;
      if (cnt >= n)
        break;
    }

    return Collections.unmodifiableSortedSet(entries);
  }

  /**
   * Returns the top-scoring entry.
   * 
   * @return the top-scoring entry
   */
  public Map.Entry<K, Double> getTopEntry() {
    return getSortedEntries().first();
  }

  /**
   * Returns the <i>i</i>th scoring entry.
   * 
   * @param i
   *            the rank
   * @return the <i>i</i>th scoring entry
   */
  public Map.Entry<K, Double> getEntryByRank(int i) {
    if (i > this.size())
      throw new NoSuchElementException("Error: index out of bounds");

    Iterator<Map.Entry<K, Double>> iter = getSortedEntries().iterator();

    int n = 0;
    while (n++ < i - 1)
      iter.next();

    return iter.next();
  }

  /**
   * Returns a list of the keys, sorted by score.
   * 
   * @return a list of the keys, sorted by score
   */
  public List<K> getSortedKeys() {
    List<K> list = new ArrayList<K>();

    for (Map.Entry<K, Double> entry : getSortedEntries()) {
      list.add(entry.getKey());
    }

    return list;
  }

  /**
   * Normalizes all scores to a value between zero and one. Note that if all
   * keys have a single score, no action is performed.
   */
  public void normalizeScores() {
    double max = Double.NEGATIVE_INFINITY;
    double min = Double.POSITIVE_INFINITY;

    for (Map.Entry<K, Double> entry : this.entrySet()) {
      double score = entry.getValue();

      if (score > max)
        max = score;

      if (score < min)
        min = score;

    }

    // if there's only one value, then meaningless to normalize
    if (max == min)
      return;

    for (Map.Entry<K, Double> entry : this.entrySet()) {
      K cur = entry.getKey();
      double score = entry.getValue();

      this.put(cur, (score - min) / (max - min));
    }

  }

  /**
   * Returns a new <code>ScoreSortedMap</code> where the score of each key
   * in this object has been linearly interpolated with scores drawn from
   * another <code>ScoreSortedMap</code>. A weight of <code>lambda</code>
   * is given to the score from this object, and a weight of (1-<code>lambda</code>)
   * is given to the score from the other <code>ScoreSortedMap</code>. Both
   * <code>ScoreSortedMap</code>s are first normalized. Note that if a key
   * is not contained in this object, but present in the other
   * <code>ScoreSortedMap</code>, it will <b>not</b> be present in the new
   * <code>ScoreSortedMap</code>.
   * 
   * @param s
   *            the other <code>ScoreSortedMap</code>
   * @param lambda
   *            weight assigned to scores from this object
   * @return a new <code>ScoreSortedMap</code> with linearly-interpolated
   *         scores
   */
  public ScoreSortedMap<K> linearInterpolationWith(ScoreSortedMap<K> s,
      double lambda) {
    this.normalizeScores();
    s.normalizeScores();

    ScoreSortedMap<K> entries = new ScoreSortedMap<K>();

    for (Map.Entry<K, Double> entry : getSortedEntries()) {
      double score1 = entry.getValue();
      double score2 = 0.0d;

      if (s.containsKey(entry.getKey())) {
        score2 = s.get(entry.getKey());
      }

      double newscore = lambda * score1 + (1 - lambda) * score2;
      // System.out.println(lambda + " * " + score1 + " + (1-" + lambda +
      // ") * " + score2 + " = " + newscore);
      entries.put(entry.getKey(), newscore);
    }

    return entries;
  }

}