Line data    Source code

       1              : #ifndef ROUTING_KIT_INVERSE_VECTOR_H
       2              : #define ROUTING_KIT_INVERSE_VECTOR_H
       3              : 
       4              : #include <routingkit/sort.h>
       5              : #include <routingkit/min_max.h>
       6              : 
       7              : #include <assert.h>
       8              : #include <algorithm>
       9              : #include <vector>
      10              : 
      11              : namespace RoutingKit{
      12              : 
      13              : //
      14              : // The inverse vector p of a vector v is a vector such that the elements
      15              : // v[p[i]], v[p[i]+1], v[p[i]+2], ..., v[p[i+1]-1] are exactly the elements
      16              : // with value i in v. If i does not occur in v, then p[i] == p[i+1]. v must be
      17              : // a sorted vector of unsigned integers.
      18              : //
      19              : 
      20              : inline
      21        34540 : std::vector<unsigned>invert_vector(const std::vector<unsigned>&v, unsigned element_count){
      22        34540 :         std::vector<unsigned>index(element_count+1);
      23        34540 :         if(v.empty()){
      24              :                 std::fill(index.begin(), index.end(), 0);
      25              :         }else{
      26              :                 assert(is_sorted_using_less(v));
      27              :                 assert(max_element_of(v) < element_count);
      28              : 
      29        12987 :                 index[0] = 0;
      30              : 
      31              :                 unsigned pos = 0;
      32       191567 :                 for(unsigned i=0; i<element_count; ++i){
      33       938875 :                         while(pos < v.size() && v[pos] < i)
      34       760295 :                                 ++pos;
      35       178580 :                         index[i] = pos;
      36              :                 }
      37        12987 :                 index[element_count] = v.size();
      38              :         }
      39        34540 :         return index;
      40              : }
      41              : 
      42              : inline
      43              : std::vector<unsigned>invert_inverse_vector(const std::vector<unsigned>&sorted_index){
      44              :         assert(!sorted_index.empty());
      45              : 
      46              :         std::vector<unsigned>v(sorted_index.back());
      47              : 
      48              :         for(unsigned i=0; i<sorted_index.size()-1; ++i)
      49              :                 for(unsigned j=sorted_index[i]; j<sorted_index[i+1]; ++j)
      50              :                         v[j] = i;
      51              : 
      52              :         return v;
      53              : }
      54              : 
      55              : } // RoutingKit
      56              : 
      57              : #endif
      58              :