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. | 1 // Convert a list of N elements with K distinct elements to [origin .. origin+K)
2 // O(N log N), but doesn't incur the overhead of std::map. | 2 // preserving the original order. O(N log N), but doesn't incur the overhead of
3 // Tested: TCO 2012 R2C Mid | 3 // Tested: TCO 2012 R2C Mid, SRM 584 Mid
4 4
5 template<typename T> 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 for(int i=0; i<xs.size(); ++i) 9 for(int i=0; i<xs.size(); ++i)
10 xi.push_back( make_pair(xs[i], i) ); 10 xi.push_back( make_pair(xs[i], i) );
11 sort(xi.begin(), xi.end()); 11 sort(xi.begin(), xi.end());
12 12
13 std::vector<int> result(xs.size()); | 13 vector<int> result(xs.size());
14 for(int k=0; k<xi.size(); ++k) | 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;
15 result[xi[k].second] = k; | 17 result[xi[k].second] = id;
> 18 }
16 return result; 19 return result;
17 } 20 }