/*
 * LensKit, an open source recommender systems toolkit.
 * Copyright 2010-2013 Regents of the University of Minnesota and contributors
 * Work on LensKit has been funded by the National Science Foundation under
 * grants IIS 05-34939, 08-08692, 08-12148, and 10-17697.
 *
 * 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 it.unimi.dsi.fastutil.longs.*;
import org.grouplens.lenskit.scored.ScoredId;
import org.grouplens.lenskit.scored.ScoredIdListBuilder;
import org.grouplens.lenskit.scored.ScoredIds;
import org.grouplens.lenskit.vectors.MutableSparseVector;

import java.util.List;

/**
 * Accumulate the top <i>N</i> scored IDs.  IDs are sorted by their associated
 * scores.
 *
 * @author <a href="http://www.grouplens.org">GroupLens Research</a>
 */
final public class TopNScoredItemAccumulator implements ScoredItemAccumulator {
    private final int count;
    private double[] scores;
    private long[] items;
    private int slot;
    private int size;
    private DoubleHeapIndirectPriorityQueue heap;

    /**
     * Create a new accumulator to accumulate the top {@var n} IDs.
     *
     * @param n The number of IDs to retain.
     */
    public TopNScoredItemAccumulator(int n) {
        this.count = n;
        // arrays must have n+1 slots to hold extra item before removing smallest
        scores = new double[n + 1];
        items = new long[n + 1];
        slot = 0;
        size = 0;
        heap = new DoubleHeapIndirectPriorityQueue(scores);
    }

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

    @Override
    public int size() {
        return size;
    }

    @Override
    public void put(long item, double score) {
        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] = item;
        scores[slot] = score;
        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;
        }
    }

    @Override
    public List<ScoredId> finish() {
        assert size == heap.size();
        int[] indices = new int[size];
        // Copy backwards so the scored list is sorted.
        for (int i = size - 1; i >= 0; i--) {
            indices[i] = heap.dequeue();
        }
        ScoredIdListBuilder bld = ScoredIds.newListBuilder(size);
        for (int i : indices) {
            bld.add(items[i], scores[i]);
        }

        assert heap.isEmpty();

        size = 0;
        slot = 0;
        return bld.finish();
    }

    @Override
    public MutableSparseVector finishVector() {
        if (scores == null) {
            return MutableSparseVector.create();
        }

        assert size == heap.size();
        int[] indices = new int[size];
        // Copy backwards so the scored list is sorted.
        for (int i = size - 1; i >= 0; i--) {
            indices[i] = heap.dequeue();
        }
        assert heap.isEmpty();

        long[] keys = new long[indices.length];
        double[] values = new double[indices.length];
        for (int i = 0; i < indices.length; i++) {
            keys[i] = items[indices[i]];
            values[i] = scores[indices[i]];
        }
        size = 0;
        slot = 0;

        return MutableSparseVector.wrapUnsorted(keys, values);
    }

    @Override
    public LongSet finishSet() {
        assert size == heap.size();

        LongSet longs = new LongOpenHashSet(size);
        while (!heap.isEmpty()) {
            longs.add(items[heap.dequeue()]);
        }

        size = 0;
        slot = 0;
        return longs;
    }
}

@@ -1140,17 +1140,142 @@
 l.longs.
-*
+LongOpenHashSet;%0Aimport it.unimi.dsi.fastutil.longs.LongSet;%0Aimport org.grouplens.lenskit.collections.CompactableLongArrayList
 ;%0Aimport
@@ -1675,20 +1675,20 @@
  */%0A
-final 
 public
+ final
  cla
@@ -1821,22 +1821,40 @@
 private 
-long%5B%5D
+CompactableLongArrayList
  items;%0A
@@ -2296,19 +2296,34 @@
 new 
-long%5Bn + 1%5D
+CompactableLongArrayList()
 ;%0A  
@@ -2874,26 +2874,125 @@
    i
-tems%5B
+f (slot == items.size()) %7B%0A            items.add(item);%0A        %7D else %7B%0A            items.set(
 slot
-%5D =
+,
  item
-;
+);%0A        %7D
 %0A   
@@ -3729,19 +3729,23 @@
 dd(items
-%5Bi%5D
+.get(i)
 , scores
@@ -3821,32 +3821,56 @@
       slot = 0;%0A
+        items.clear();%0A%0A
         return b
@@ -4481,17 +4481,21 @@
  = items
-%5B
+.get(
 indices%5B
@@ -4488,33 +4488,33 @@
 s.get(indices%5Bi%5D
-%5D
+)
 ;%0A            va
@@ -4588,16 +4588,39 @@
 lot = 0;
+%0A        items.clear();
 %0A%0A      
@@ -4879,17 +4879,21 @@
 dd(items
-%5B
+.get(
 heap.deq
@@ -4898,17 +4898,17 @@
 equeue()
-%5D
+)
 );%0A     
@@ -4941,32 +4941,56 @@
       slot = 0;%0A
+        items.clear();%0A%0A
         return l

Make top-N accumulator use compact item lists