1.1.4 Coordinate Compression

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177

/*

Given a range of $n$ numerical elements, reassign each element to an integer in the domain $[0, k)$,
where $k$ is the number of distinct elements in the original range, while preserving the initial
relative ordering of elements. That is, if $a$ is the array of original values and $b$ is the array
of compressed values, then every pair of indices $i, j$ in $[0, n)$ shall satisfy $a[i] < a[j]$ if
and only if $b[i] < b[j]$.

The two functions below take a ForwardIterator range, rewrite it in place, and discard the mapping.
The comparator `comp` defines the value ordering: `comp(a, b)` is true when `a` precedes `b`.

- `compress1(lo, hi, comp = std::less<>())` performs the compression by sorting the array, removing
  duplicates, and binary searching for the position of each original value.
- `compress2(lo, hi, comp = std::less<>())` achieves the same result by inserting all values into an
  `std::map`, which automatically removes duplicate values and supports efficient lookups of the
  compressed values.

Time Complexity:
- O(n log n) per call to `compress1(lo, hi)` and `compress2(lo, hi)`, where $n$ is the distance
  between `lo` and `hi`.

Space Complexity:
- O(n) auxiliary for `compress1()` and `compress2()`.

*/

#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <map>
#include <vector>

template<typename It, typename Compare = std::less<>>
void compress1(It lo, It hi, Compare comp = Compare{}) {
  using T = typename std::iterator_traits<It>::value_type;
  std::vector<T> v(lo, hi);
  std::sort(v.begin(), v.end(), comp);
  v.erase(
      std::unique(
          v.begin(), v.end(), [&](const T &a, const T &b) { return !comp(a, b) && !comp(b, a); }
      ),
      v.end()
  );
  for (It it = lo; it != hi; ++it) {
    *it = static_cast<int>(std::lower_bound(v.begin(), v.end(), *it, comp) - v.begin());
  }
}

template<typename It, typename Compare = std::less<>>
void compress2(It lo, It hi, Compare comp = Compare{}) {
  using T = typename std::iterator_traits<It>::value_type;
  std::map<T, int, Compare> m(comp);
  for (It it = lo; it != hi; ++it) {
    m[*it] = 0;
  }
  int id = 0;
  for (auto &[key, val] : m) {
    val = id++;
  }
  for (It it = lo; it != hi; ++it) {
    *it = m[*it];
  }
}

/*

`Compressor` retains the sorted table of distinct values so that arbitrary values can be mapped to
and from compressed ranks long after construction, such as for offline queries arriving separately
from the array being compressed. It uses `std::less<T>` by default; to customize the ordering,
instantiate `Compressor<T, Compare>` and pass the comparator to either constructor.

- `Compressor<T>()` constructs an empty compressor. Register values with `add(x)`, then call
  `build()` once before the first query.
- `Compressor<T>(lo, hi)` constructs a compressor from the half-open iterator range $[`lo`, `hi`)$.
- `size()` returns the number of distinct registered values $k$.
- `value(r)` returns the original value with rank `r`, inverting `rank()`.
- `contains(x)` returns whether `x` is a registered value.
- `rank(x)` returns the compressed value (rank) of `x` in $[0, k)$. `x` must have been registered.

Time Complexity:
- O(n log n) per call to `Compressor(lo, hi)`, where $n$ is the range length.
- O(1) amortized per call to `add()`, and O(m log m) per call to `build()`, where $m$ is the total
  number of values registered.
- O(log k) per call to `rank()` and `contains()`, where $k$ is the number of distinct values.
- O(1) per call to `size()` and `value()`.

Space Complexity:
- O(k) storage, where $k$ is the number of distinct registered values.

*/

template<typename T, typename Compare = std::less<T>>
class Compressor {
  Compare comp;
  std::vector<T> v;

 public:
  explicit Compressor(Compare comp = Compare{}) : comp(std::move(comp)) {}

  template<typename It>
  Compressor(It lo, It hi, Compare comp = Compare{}) : comp(std::move(comp)), v(lo, hi) {
    build();
  }

  void build() {
    std::sort(v.begin(), v.end(), comp);
    v.erase(
        std::unique(
            v.begin(), v.end(), [&](const T &a, const T &b) { return !comp(a, b) && !comp(b, a); }
        ),
        v.end()
    );
  }

  void add(const T &x) { v.push_back(x); }
  int size() const { return static_cast<int>(v.size()); }
  const T &value(int r) const { return v[r]; }
  bool contains(const T &x) const { return std::binary_search(v.begin(), v.end(), x, comp); }

  int rank(const T &x) const {
    int r = static_cast<int>(std::lower_bound(v.begin(), v.end(), x, comp) - v.begin());
    assert(r < size() && !comp(x, v[r]));  // x must be registered.
    return r;
  }
};

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  {
    vector<int> a{1, 30, 30, 7, 9, 8, 99, 99};
    compress1(a.begin(), a.end());
    assert((a == vector<int>{0, 4, 4, 1, 3, 2, 5, 5}));
  }
  {
    vector<int> a{1, 30, 30, 7, 9, 8, 99, 99};
    compress2(a.begin(), a.end());
    assert((a == vector<int>{0, 4, 4, 1, 3, 2, 5, 5}));
  }
  {  // Non-integral types work too, as long as ints can be assigned to them.
    vector<double> a{0.5, -1.0, 3, -1.0, 20, 0.5};
    compress1(a.begin(), a.end());
    assert((a == vector<double>{1, 0, 2, 0, 3, 1}));
  }
  {
    vector<int> a{10, 5, 30, 5, 20};
    Compressor<int> cc(a.begin(), a.end());
    assert(cc.size() == 4);
    assert(cc.rank(5) == 0);
    assert(cc.rank(30) == 3);
    assert(cc.value(2) == 20);
    assert(cc.contains(10) && !cc.contains(7));
  }
  {  // Register values incrementally, then build once before querying.
    Compressor<double> cc;
    cc.add(0.5);
    cc.add(-1.0);
    cc.add(0.5);
    cc.build();
    assert(cc.size() == 2);
    assert(cc.rank(0.5) == 1);
    assert(cc.value(0) == -1.0);
  }
  {
    vector<int> a{10, 30, 20, 10};
    Compressor<int, greater<int>> cc(a.begin(), a.end());
    assert(cc.rank(30) == 0 && cc.rank(10) == 2);
    assert(cc.value(1) == 20);
    compress1(a.begin(), a.end(), greater<int>());
    assert((a == vector<int>{2, 0, 1, 2}));
  }
  return 0;
}