• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Modified lib/typical/coordinate_compression.cpp from [5adf500ce372739d] to [60ffa78d3698d241].

    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  }