1 // Copyright 2018 Google Inc. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15
16 // Author: ericv@google.com (Eric Veach)
17
18 #include "s2/encoded_s2cell_id_vector.h"
19
20 #include <vector>
21 #include <gtest/gtest.h>
22 #include "s2/third_party/absl/memory/memory.h"
23 #include "s2/s2loop.h"
24 #include "s2/s2pointutil.h"
25 #include "s2/s2shape_index.h"
26 #include "s2/s2testing.h"
27 #include "s2/s2text_format.h"
28
29 using absl::make_unique;
30 using s2textformat::MakeCellIdOrDie;
31 using std::vector;
32
33 namespace s2coding {
34
35 // Encodes the given vector and returns the corresponding
36 // EncodedS2CellIdVector (which points into the Encoder's data buffer).
MakeEncodedS2CellIdVector(const vector<S2CellId> & input,Encoder * encoder)37 EncodedS2CellIdVector MakeEncodedS2CellIdVector(const vector<S2CellId>& input,
38 Encoder* encoder) {
39 EncodeS2CellIdVector(input, encoder);
40 Decoder decoder(encoder->base(), encoder->length());
41 EncodedS2CellIdVector cell_ids;
42 EXPECT_TRUE(cell_ids.Init(&decoder));
43 return cell_ids;
44 }
45
46 // Encodes the given vector and checks that it has the expected size and
47 // contents.
TestEncodedS2CellIdVector(const vector<S2CellId> & expected,size_t expected_bytes)48 void TestEncodedS2CellIdVector(const vector<S2CellId>& expected,
49 size_t expected_bytes) {
50 Encoder encoder;
51 EncodedS2CellIdVector actual = MakeEncodedS2CellIdVector(expected, &encoder);
52 EXPECT_EQ(expected_bytes, encoder.length());
53 EXPECT_EQ(actual.Decode(), expected);
54 }
55
56 // Like the above, but accepts a vector<uint64> rather than a vector<S2CellId>.
TestEncodedS2CellIdVector(const vector<uint64> & raw_expected,size_t expected_bytes)57 void TestEncodedS2CellIdVector(const vector<uint64>& raw_expected,
58 size_t expected_bytes) {
59 vector<S2CellId> expected;
60 for (uint64 raw_id : raw_expected) {
61 expected.push_back(S2CellId(raw_id));
62 }
63 TestEncodedS2CellIdVector(expected, expected_bytes);
64 }
65
TEST(EncodedS2CellIdVector,Empty)66 TEST(EncodedS2CellIdVector, Empty) {
67 TestEncodedS2CellIdVector(vector<S2CellId>{}, 2);
68 }
69
TEST(EncodedS2CellIdVector,None)70 TEST(EncodedS2CellIdVector, None) {
71 TestEncodedS2CellIdVector({S2CellId::None()}, 3);
72 }
73
TEST(EncodedS2CellIdVector,NoneNone)74 TEST(EncodedS2CellIdVector, NoneNone) {
75 TestEncodedS2CellIdVector({S2CellId::None(), S2CellId::None()}, 4);
76 }
77
TEST(EncodedS2CellIdVector,Sentinel)78 TEST(EncodedS2CellIdVector, Sentinel) {
79 TestEncodedS2CellIdVector({S2CellId::Sentinel()}, 10);
80 }
81
TEST(EncodedS2CellIdVector,MaximumShiftCell)82 TEST(EncodedS2CellIdVector, MaximumShiftCell) {
83 // Tests the encoding of a single cell at level 2, which corresponds the
84 // maximum encodable shift value (56).
85 TestEncodedS2CellIdVector({MakeCellIdOrDie("0/00")}, 3);
86 }
87
TEST(EncodedS2CellIdVector,SentinelSentinel)88 TEST(EncodedS2CellIdVector, SentinelSentinel) {
89 TestEncodedS2CellIdVector({S2CellId::Sentinel(), S2CellId::Sentinel()}, 11);
90 }
91
TEST(EncodedS2CellIdVector,NoneSentinelNone)92 TEST(EncodedS2CellIdVector, NoneSentinelNone) {
93 TestEncodedS2CellIdVector(
94 {S2CellId::None(), S2CellId::Sentinel(), S2CellId::None()}, 26);
95 }
96
TEST(EncodedS2CellIdVector,InvalidCells)97 TEST(EncodedS2CellIdVector, InvalidCells) {
98 // Tests that cells with an invalid LSB can be encoded.
99 TestEncodedS2CellIdVector({0x6, 0xe, 0x7e}, 5);
100 }
101
TEST(EncodedS2CellIdVector,OneByteLeafCells)102 TEST(EncodedS2CellIdVector, OneByteLeafCells) {
103 // Tests that (1) if all cells are leaf cells, the low bit is not encoded,
104 // and (2) this can be indicated using the standard 1-byte header.
105 TestEncodedS2CellIdVector({0x3, 0x7, 0x177}, 5);
106 }
107
TEST(EncodedS2CellIdVector,OneByteLevel29Cells)108 TEST(EncodedS2CellIdVector, OneByteLevel29Cells) {
109 // Tests that (1) if all cells are at level 29, the low bit is not encoded,
110 // and (2) this can be indicated using the standard 1-byte header.
111 TestEncodedS2CellIdVector({0xc, 0x1c, 0x47c}, 5);
112 }
113
TEST(EncodedS2CellIdVector,OneByteLevel28Cells)114 TEST(EncodedS2CellIdVector, OneByteLevel28Cells) {
115 // Tests that (1) if all cells are at level 28, the low bit is not encoded,
116 // and (2) this can be indicated using the extended 2-byte header.
117 TestEncodedS2CellIdVector({0x30, 0x70, 0x1770}, 6);
118 }
119
TEST(EncodedS2CellIdVector,OneByteMixedCellLevels)120 TEST(EncodedS2CellIdVector, OneByteMixedCellLevels) {
121 // Tests that cells at mixed levels can be encoded in one byte.
122 TestEncodedS2CellIdVector({0x300, 0x1c00, 0x7000, 0xff00}, 6);
123 }
124
TEST(EncodedS2CellIdVector,OneByteMixedCellLevelsWithPrefix)125 TEST(EncodedS2CellIdVector, OneByteMixedCellLevelsWithPrefix) {
126 // Tests that cells at mixed levels can be encoded in one byte even when
127 // they share a multi-byte prefix.
128 TestEncodedS2CellIdVector({
129 0x1234567800000300, 0x1234567800001c00,
130 0x1234567800007000, 0x123456780000ff00}, 10);
131 }
132
TEST(EncodedS2CellIdVector,OneByteRangeWithBaseValue)133 TEST(EncodedS2CellIdVector, OneByteRangeWithBaseValue) {
134 // Tests that cells can be encoded in one byte by choosing a base value
135 // whose bit range overlaps the delta values.
136 // 1 byte header, 3 bytes base, 1 byte size, 4 bytes deltas
137 TestEncodedS2CellIdVector({
138 0x00ffff0000000000, 0x0100fc0000000000,
139 0x0100500000000000, 0x0100330000000000}, 9);
140 }
141
TEST(EncodedS2CellIdVector,SixFaceCells)142 TEST(EncodedS2CellIdVector, SixFaceCells) {
143 vector<S2CellId> ids;
144 for (int face = 0; face < 6; ++face) {
145 ids.push_back(S2CellId::FromFace(face));
146 }
147 TestEncodedS2CellIdVector(ids, 8);
148 }
149
TEST(EncodedS2CellIdVector,FourLevel10Children)150 TEST(EncodedS2CellIdVector, FourLevel10Children) {
151 vector<S2CellId> ids;
152 S2CellId parent = MakeCellIdOrDie("3/012301230");
153 for (S2CellId id = parent.child_begin();
154 id != parent.child_end(); id = id.next()) {
155 ids.push_back(id);
156 }
157 TestEncodedS2CellIdVector(ids, 8);
158 }
159
TEST(EncodedS2CellIdVector,FractalS2ShapeIndexCells)160 TEST(EncodedS2CellIdVector, FractalS2ShapeIndexCells) {
161 S2Testing::Fractal fractal;
162 fractal.SetLevelForApproxMaxEdges(3 * 1024);
163 S2Point center = s2textformat::MakePointOrDie("47.677:-122.206");
164 MutableS2ShapeIndex index;
165 index.Add(make_unique<S2Loop::OwningShape>(
166 fractal.MakeLoop(S2::GetFrame(center), S1Angle::Degrees(1))));
167 vector<S2CellId> ids;
168 for (MutableS2ShapeIndex::Iterator it(&index, S2ShapeIndex::BEGIN);
169 !it.done(); it.Next()) {
170 ids.push_back(it.id());
171 }
172 EXPECT_EQ(966, ids.size());
173 TestEncodedS2CellIdVector(ids, 2902);
174 }
175
TEST(EncodedS2CellIdVector,CoveringCells)176 TEST(EncodedS2CellIdVector, CoveringCells) {
177 vector<uint64> ids {
178 0x414a617f00000000, 0x414a61c000000000, 0x414a624000000000,
179 0x414a63c000000000, 0x414a647000000000, 0x414a64c000000000,
180 0x414a653000000000, 0x414a704000000000, 0x414a70c000000000,
181 0x414a714000000000, 0x414a71b000000000, 0x414a7a7c00000000,
182 0x414a7ac000000000, 0x414a8a4000000000, 0x414a8bc000000000,
183 0x414a8c4000000000, 0x414a8d7000000000, 0x414a8dc000000000,
184 0x414a914000000000, 0x414a91c000000000, 0x414a924000000000,
185 0x414a942c00000000, 0x414a95c000000000, 0x414a96c000000000,
186 0x414ab0c000000000, 0x414ab14000000000, 0x414ab34000000000,
187 0x414ab3c000000000, 0x414ab44000000000, 0x414ab4c000000000,
188 0x414ab6c000000000, 0x414ab74000000000, 0x414ab8c000000000,
189 0x414ab94000000000, 0x414aba1000000000, 0x414aba3000000000,
190 0x414abbc000000000, 0x414abe4000000000, 0x414abec000000000,
191 0x414abf4000000000, 0x46b5454000000000, 0x46b545c000000000,
192 0x46b5464000000000, 0x46b547c000000000, 0x46b5487000000000,
193 0x46b548c000000000, 0x46b5494000000000, 0x46b54a5400000000,
194 0x46b54ac000000000, 0x46b54b4000000000, 0x46b54bc000000000,
195 0x46b54c7000000000, 0x46b54c8004000000, 0x46b54ec000000000,
196 0x46b55ad400000000, 0x46b55b4000000000, 0x46b55bc000000000,
197 0x46b55c4000000000, 0x46b55c8100000000, 0x46b55dc000000000,
198 0x46b55e4000000000, 0x46b5604000000000, 0x46b560c000000000,
199 0x46b561c000000000, 0x46ca424000000000, 0x46ca42c000000000,
200 0x46ca43c000000000, 0x46ca444000000000, 0x46ca45c000000000,
201 0x46ca467000000000, 0x46ca469000000000, 0x46ca5fc000000000,
202 0x46ca604000000000, 0x46ca60c000000000, 0x46ca674000000000,
203 0x46ca679000000000, 0x46ca67f000000000, 0x46ca684000000000,
204 0x46ca855000000000, 0x46ca8c4000000000, 0x46ca8cc000000000,
205 0x46ca8e5400000000, 0x46ca8ec000000000, 0x46ca8f0100000000,
206 0x46ca8fc000000000, 0x46ca900400000000, 0x46ca98c000000000,
207 0x46ca994000000000, 0x46ca99c000000000, 0x46ca9a4000000000,
208 0x46ca9ac000000000, 0x46ca9bd500000000, 0x46ca9e4000000000,
209 0x46ca9ec000000000, 0x46caf34000000000, 0x46caf4c000000000,
210 0x46caf54000000000
211 };
212 EXPECT_EQ(97, ids.size());
213 TestEncodedS2CellIdVector(ids, 488);
214 }
215
TEST(EncodedS2CellIdVector,LowerBoundLimits)216 TEST(EncodedS2CellIdVector, LowerBoundLimits) {
217 // Test seeking before the beginning and past the end of the vector.
218 S2CellId first = S2CellId::Begin(S2CellId::kMaxLevel);
219 S2CellId last = S2CellId::End(S2CellId::kMaxLevel).prev();
220 Encoder encoder;
221 EncodedS2CellIdVector cell_ids = MakeEncodedS2CellIdVector(
222 {first, last}, &encoder);
223 EXPECT_EQ(0, cell_ids.lower_bound(S2CellId::None()));
224 EXPECT_EQ(0, cell_ids.lower_bound(first));
225 EXPECT_EQ(1, cell_ids.lower_bound(first.next()));
226 EXPECT_EQ(1, cell_ids.lower_bound(last.prev()));
227 EXPECT_EQ(1, cell_ids.lower_bound(last));
228 EXPECT_EQ(2, cell_ids.lower_bound(last.next()));
229 EXPECT_EQ(2, cell_ids.lower_bound(S2CellId::Sentinel()));
230 }
231
232 } // namespace s2coding
233