Struct TopN

Given a set of data points entered through the put function, this output range maintains the invariant that the top N according to compFun will be contained in the data structure. Uses a heap internally, O(log N) insertion time. Good for finding the largest/smallest N elements of a very large dataset that cannot be sorted quickly in its entirety, and may not even fit in memory. If less than N datapoints have been entered, all are contained in the structure.

struct TopN(T, alias compFun) ;

Constructors

NameDescription
this The variable ntop controls how many elements are retained.

Fields

NameTypeDescription
n uint
nAdded uint
nodes T[]

Methods

NameDescription
getElements Get the elements currently in the struct. Returns a reference to internal state, elements will be in an arbitrary order. Cheap.
getSorted Returns the elements sorted by compFun. The array returned is a duplicate of the input array. Not cheap.
put Insert an element into the topN struct.

Aliases

NameDescription
comp

Examples

Random gen;
gen.seed(unpredictableSeed);
uint[] nums = seq(0U, 100U);
auto less = TopN!(uint, "a < b")(10);
auto more = TopN!(uint, "a > b")(10);
randomShuffle(nums, gen);
foreach(n; nums) {
    less.put(n);
    more.put(n);
}
 assert(less.getSorted == [0U, 1,2,3,4,5,6,7,8,9]);
 assert(more.getSorted == [99U, 98, 97, 96, 95, 94, 93, 92, 91, 90]);