Differences From Artifact [5adf500ce372739d]:
- File
lib/typical/coordinate_compression.cpp
- 2012-06-07 14:24:24 - part of checkin [34dd53bac9] on branch trunk - TCO12-2C (user: kinaba) [annotate]
To Artifact [60ffa78d3698d241]:
- File
lib/typical/coordinate_compression.cpp
- 2013-07-10 13:36:20 - part of checkin [2cbc47d903] on branch trunk - Coordinate Compression for duplicated elements. (user: kinaba) [annotate]
1 -// Convert a list of distinct elements to [0..N), preserving the original order.
2 -// O(N log N), but doesn't incur the overhead of std::map.
3 -// Tested: TCO 2012 R2C Mid
1 +// Convert a list of N elements with K distinct elements to [origin .. origin+K),
2 +// preserving the original order. O(N log N), but doesn't incur the overhead of std::map.
3 +// Tested: TCO 2012 R2C Mid, SRM 584 Mid
4 4
5 5 template<typename T>
6 -std::vector<int> compress(std::vector<T>& xs)
6 +vector<int> compress(const vector<T>& xs, int origin = 0)
7 7 {
8 - std::vector< pair<T,int> > xi;
8 + vector< pair<T,int> > xi;
9 9 for(int i=0; i<xs.size(); ++i)
10 10 xi.push_back( make_pair(xs[i], i) );
11 11 sort(xi.begin(), xi.end());
12 12
13 - std::vector<int> result(xs.size());
14 - for(int k=0; k<xi.size(); ++k)
15 - result[xi[k].second] = k;
13 + vector<int> result(xs.size());
14 + for(int k=0,id=origin; k<xi.size(); ++k) {
15 + if(0<=k-1 && xi[k-1].first<xi[k].first)
16 + ++id;
17 + result[xi[k].second] = id;
18 + }
16 19 return result;
17 20 }