/*
 * LensKit, a reference implementation of recommender algorithms.
 * Copyright 2010-2011 Regents of the University of Minnesota
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 2.1 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program; if not, write to the Free Software Foundation, Inc., 51
 * Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */
package org.grouplens.lenskit.util;

import it.unimi.dsi.fastutil.doubles.DoubleHeapIndirectPriorityQueue;

import org.grouplens.lenskit.data.ScoredLongArrayList;
import org.grouplens.lenskit.data.ScoredLongList;

/**
 * Accumulate the top <i>N</i> scored IDs.
 * @author Michael Ekstrand <ekstrand@cs.umn.edu>
 *
 */
public class ScoredItemAccumulator {
    private static final long serialVersionUID = -3045709409904317792L;
    private final int count;
    private double[] scores;
    private long[] items;
    private int slot;
    private int size;
    private DoubleHeapIndirectPriorityQueue heap;

    public ScoredItemAccumulator(int n) {
        this.count = n;
        scores = new double[n+1];
        items = new long[n+1];
        slot = 0;
        size = 0;
        heap = new DoubleHeapIndirectPriorityQueue(scores);
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void put(long i, double val) {
        assert slot <= count;
        assert heap.size() == size;
        /* Store the new item. The slot shows where the current item is,
         * and then we deal with it based on whether we're oversized.
         */
        items[slot] = i;
        scores[slot] = val;
        heap.enqueue(slot);

        if (size == count) {
            // already at capacity, so remove and reuse smallest item
            slot = heap.dequeue();
        } else {
            // we have free space, so increment the slot and size
            slot += 1;
            size += 1;
        }
    }
    
    /**
     * Accumulate the scores into a sorted scored list and reset the accumulator.
     * @return The sorted, scored list of items.
     */
    public ScoredLongList finish() {
        assert size == heap.size();
        int[] indices = new int[size];
        for (int i = size - 1; i >= 0; i--) {
            indices[i] = heap.dequeue();
        }
        ScoredLongList l = new ScoredLongArrayList(size);
        for (int i: indices) {
            l.add(items[i], scores[i]);
        }
        
        size = 0;
        slot = 0;
        return l;
    }
}

@@ -1117,16 +1117,67 @@
 red IDs.
+  IDs are sorted by their associated%0A * scores.%0A * 
 %0A * @aut
@@ -1267,80 +1267,8 @@
 r %7B%0A
-    private static final long serialVersionUID = -3045709409904317792L;%0A
     
@@ -1442,16 +1442,149 @@
  heap;%0A%0A
+    /**%0A     * Create a new accumulator to accumulate the top %3Cvar%3En%3C/var%3E IDs.%0A     * @param n The number of IDs to retain.%0A     */%0A
     publ
@@ -1817,119 +1817,737 @@
     
-public boolean isEmpty() %7B%0A        return size == 0;%0A    %7D%0A%0A    public int size() %7B%0A        return size;%0A    %7D%0A
+/**%0A     * Query whether the accumulator is empty.%0A     * @return %3Ctt%3Etrue%3C/tt%3E if the accumulator has no items.%0A     */%0A    public boolean isEmpty() %7B%0A        return size == 0;%0A    %7D%0A%0A    /**%0A     * Get the number of items in the accumulator.%0A     * %0A     * @return The number of items accumulated so far, up to the maximum items%0A     *         desired from the accumulator.%0A     */%0A    public int size() %7B%0A        return size;%0A    %7D%0A%0A    /**%0A     * Put a new item in the accumulator. Putting the same item twice does%0A     * %3Cstrong%3Enot%3C/strong%3E replace the previous entry - it adds a new entry%0A     * with the same ID.%0A     * %0A     * @param item The item to add to the accumulator.%0A     * @param score The item's score.%0A     */
 %0A   
@@ -2569,16 +2569,19 @@
 t(long i
+tem
 , double
@@ -2581,19 +2581,21 @@
  double 
-val
+score
 ) %7B%0A    
@@ -2664,17 +2664,37 @@
         
-/
+%0A        /*%0A         
 * Store 
@@ -2748,16 +2748,20 @@
 item is,
+ and
 %0A       
@@ -2763,20 +2763,16 @@
        *
- and
  then we
@@ -2854,16 +2854,19 @@
 lot%5D = i
+tem
 ;%0A      
@@ -2886,11 +2886,13 @@
 %5D = 
-val
+score
 ;%0A  
@@ -3274,24 +3274,31 @@
 nd reset the
+%0A     *
  accumulator
@@ -3291,32 +3291,40 @@
  * accumulator.%0A
+     * %0A
      * @return T

Document and clean up the scored item accumulator.