edu.stanford.math.plex4.metric.impl

Class TruncatedPriorityQueue<T>

java.lang.Object

edu.stanford.math.plex4.metric.impl.TruncatedPriorityQueue<T>

Type Parameters:

T - the index type

public class TruncatedPriorityQueue<T>
extends java.lang.Object

This class is used for holding the set of k-indices with the lowest ranks or values. It is used by adding elements along with their ranks. It stores a maximum of k values, and discards all values that are not in the lowest k.

An example of a use of this class is for maintaining a list of k-nearest neighbors.

Author:

Andrew Tausz

Constructor Summary

Constructors

Constructor and Description
TruncatedPriorityQueue(int k)

Method Summary

Methods

Modifier and Type	Method and Description
java.util.List<T>	getIndices() This function returns the list of indices currently in the queue.
java.util.List<edu.stanford.math.primitivelib.autogen.pair.ObjectDoublePair<T>>	getListOfPairs() This function returns the list of object-value pairs currently in the queue.
void	insert(T index, double value) This function inserts the given object (or index), with a specified value into the queue.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TruncatedPriorityQueue

public TruncatedPriorityQueue(int k)

Method Detail

getListOfPairs

public java.util.List<edu.stanford.math.primitivelib.autogen.pair.ObjectDoublePair<T>> getListOfPairs()

This function returns the list of object-value pairs currently in the queue.

Returns:

a list of object-value pairs

getIndices

public java.util.List<T> getIndices()

This function returns the list of indices currently in the queue.

Returns:

a list of indices

insert

public void insert(T index,
          double value)

This function inserts the given object (or index), with a specified value into the queue. It holds the elements in sorted order. Note, however, if the queue is already full and the value of the inserted object is higher than all of the elements in the queue, it is not actually inserted.

Examples:

list = {(a, 1), (b, 4)}. Inserting (c, 2) produces {(a, 1), (c, 2), (b, 4)}, when k >= 3. If k == 2, then the result is {(a, 1), (c, 2)}. Inserting (d, 8), with k == 2 does not modify the list.

Parameters:

index - the object to insert

value - the value of the object