Artifact 5adf500ce372739d7e7224492a70a6efbed053dd

• File lib/typical/coordinate_compression.cpp
  • 2012-06-07 14:24:24 - part of checkin [34dd53bac9] on branch trunk - TCO12-2C (user: kinaba) [annotate]

// Convert a list of distinct elements to [0..N), preserving the original order.
// O(N log N), but doesn't incur the overhead of std::map.
// Tested: TCO 2012 R2C Mid

template<typename T>
std::vector<int> compress(std::vector<T>& xs)
{
	std::vector< pair<T,int> > xi;
	for(int i=0; i<xs.size(); ++i)
		xi.push_back( make_pair(xs[i], i) );
	sort(xi.begin(), xi.end());

	std::vector<int> result(xs.size());
	for(int k=0; k<xi.size(); ++k)
		result[xi[k].second] = k;
	return result;
}