Impala Documentation

template<class C1, class C2>

void Impala::Core::Column::SortDescendingTopN	(	C1 *	first,
		C2 *	second,
		C1 *	result,
		C2 *	resultSecond
	)			`[inline]`

Sort only topN of columns first and second in descending order based on the values in the second column.

topN is determined by the capacity of the given result columns.

Definition at line 123 of file Sort.h.

References ILOG_ERROR, and ILOG_VAR.

Referenced by Impala::Core::Table::SimilarityTableSet::ComputeRanksTopN().

00124 {
00125     ILOG_VAR(Impala.Core.Column.SortDescendingTopN);
00126     if (first->Capacity() != second->Capacity())
00127     {
00128         ILOG_ERROR("Incompatible sizes");
00129         return;
00130     }
00131     if (result->Capacity() != resultSecond->Capacity())
00132     {
00133         ILOG_ERROR("Incompatible sizes");
00134         return;
00135     }
00136 
00137     int nrElem = first->Capacity();
00138     int topN = result->Capacity();
00139     result->Set(0, first->Get(0));
00140     resultSecond->Set(0, second->Get(0));
00141     int curNr = 1;
00142     for (int i=1 ; i<nrElem ; i++)
00143     {
00144         int j=0;
00145         while ((j<curNr) && (second->Get(i) < resultSecond->Get(j)))
00146         {
00147             j++;
00148         }
00149         if (j == curNr)
00150         { // is smaller than result
00151             if (curNr < topN)
00152             { // insert only when topN is not filled yet
00153                 result->Set(curNr, first->Get(i));
00154                 resultSecond->Set(curNr, second->Get(i));
00155                 curNr++;
00156             }
00157         }
00158         else
00159         { // insert at current position
00160             if (curNr < topN)
00161             { // room left, so expand
00162                 curNr++;
00163             }
00164             for (int k=curNr-1 ; k>j ; k--)
00165             { // move larger value towards end
00166                 result->Set(k, result->Get(k-1));
00167                 resultSecond->Set(k, resultSecond->Get(k-1));
00168             }
00169             result->Set(j, first->Get(i));
00170             resultSecond->Set(j, second->Get(i));
00171         }
00172     }
00173 }