Impala Documentation

template<class C1, class C2>

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

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

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

Definition at line 46 of file Sort.h.

References ILOG_ERROR, and ILOG_VAR.

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

00047 {
00048     ILOG_VAR(Impala.Core.Column.SortAscendingTopN);
00049     if (first->Capacity() != second->Capacity())
00050     {
00051         ILOG_ERROR("Incompatible sizes");
00052         return;
00053     }
00054     if (result->Capacity() != resultSecond->Capacity())
00055     {
00056         ILOG_ERROR("Incompatible sizes");
00057         return;
00058     }
00059 
00060     int nrElem = first->Capacity();
00061     int topN = result->Capacity();
00062     result->Set(0, first->Get(0));
00063     resultSecond->Set(0, second->Get(0));
00064     int curNr = 1;
00065     for (int i=1 ; i<nrElem ; i++)
00066     {
00067         int j=0;
00068         while ((j<curNr) && (second->Get(i) > resultSecond->Get(j)))
00069         {
00070             j++;
00071         }
00072         if (j == curNr)
00073         { // is larger than result
00074             if (curNr < topN)
00075             { // insert only when topN is not filled yet
00076                 result->Set(curNr, first->Get(i));
00077                 resultSecond->Set(curNr, second->Get(i));
00078                 curNr++;
00079             }
00080         }
00081         else
00082         { // insert at current position
00083             if (curNr < topN)
00084             { // room left, so expand
00085                 curNr++;
00086             }
00087             for (int k=curNr-1 ; k>j ; k--)
00088             { // move larger value towards end
00089                 result->Set(k, result->Get(k-1));
00090                 resultSecond->Set(k, resultSecond->Get(k-1));
00091             }
00092             result->Set(j, first->Get(i));
00093             resultSecond->Set(j, second->Get(i));
00094         }
00095     }
00096 }