← Back to branch summary

~evarlast/ubuntu/trusty/mongodb/upstart-workaround-debian-bug-718702

« back to all changes in this revision

Viewing changes to src/third_party/s2/s2cellunion_test.cc

  • Committer: Package Import Robot
  • Author(s): James Page, James Page, Robie Basak
  • Date: 2013-05-29 17:44:42 UTC
  • mfrom: (44.1.7 sid)
  • Revision ID: package-import@ubuntu.com-20130529174442-z0a4qmoww4y0t458
Tags: 1:2.4.3-1ubuntu1
[ James Page ]
* Merge from Debian unstable, remaining changes:
  - Enable SSL support:
    + d/control: Add libssl-dev to BD's.
    + d/rules: Enabled --ssl option.
    + d/mongodb.conf: Add example SSL configuration options.
  - d/mongodb-server.mongodb.upstart: Add upstart configuration.
  - d/rules: Don't strip binaries during scons build for Ubuntu.
  - d/control: Add armhf to target archs.
  - d/p/SConscript.client.patch: fixup install of client libraries.
  - d/p/0010-install-libs-to-usr-lib-not-usr-lib64-Closes-588557.patch:
    Install libraries to lib not lib64.
* Dropped changes:
  - d/p/arm-support.patch: Included in Debian.
  - d/p/double-alignment.patch: Included in Debian.
  - d/rules,control: Debian also builds with avaliable system libraries
    now.
* Fix FTBFS due to gcc and boost upgrades in saucy:
  - d/p/0008-ignore-unused-local-typedefs.patch: Add -Wno-unused-typedefs
    to unbreak building with g++-4.8.
  - d/p/0009-boost-1.53.patch: Fixup signed/unsigned casting issue.

[ Robie Basak ]
* d/p/0011-Use-a-signed-char-to-store-BSONType-enumerations.patch: Fixup
  build failure on ARM due to missing signed'ness of char cast.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/third_party/s2/s2cellunion_test.cc
 
1
// Copyright 2005 Google Inc. All Rights Reserved.
 
2
 
 
3
#include "s2cellunion.h"
 
4
 
 
5
#include <algorithm>
 
6
using std::min;
 
7
using std::max;
 
8
using std::swap;
 
9
using std::reverse;
 
10
 
 
11
#include <vector>
 
12
using std::vector;
 
13
 
 
14
 
 
15
#include "base/integral_types.h"
 
16
#include "base/logging.h"
 
17
#include "testing/base/public/gunit.h"
 
18
#include "s2cellid.h"
 
19
#include "s2cell.h"
 
20
#include "s2cap.h"
 
21
#include "s2testing.h"
 
22
#include "s2regioncoverer.h"
 
23
 
 
24
TEST(S2CellUnion, Basic) {
 
25
  S2CellUnion empty;
 
26
  vector<S2CellId> ids;
 
27
  empty.Init(ids);
 
28
  EXPECT_EQ(0, empty.num_cells());
 
29
 
 
30
  S2CellId face1_id = S2CellId::FromFacePosLevel(1, 0, 0);
 
31
  S2CellUnion face1_union;
 
32
  ids.push_back(face1_id);
 
33
  face1_union.Init(ids);
 
34
  EXPECT_EQ(1, face1_union.num_cells());
 
35
  EXPECT_EQ(face1_id, face1_union.cell_id(0));
 
36
 
 
37
  S2CellId face2_id = S2CellId::FromFacePosLevel(2, 0, 0);
 
38
  S2CellUnion face2_union;
 
39
  vector<uint64> cell_ids;
 
40
  cell_ids.push_back(face2_id.id());
 
41
  face2_union.Init(cell_ids);
 
42
  EXPECT_EQ(1, face2_union.num_cells());
 
43
  EXPECT_EQ(face2_id, face2_union.cell_id(0));
 
44
 
 
45
  S2Cell face1_cell(face1_id);
 
46
  S2Cell face2_cell(face2_id);
 
47
  EXPECT_TRUE(face1_union.Contains(face1_cell));
 
48
  EXPECT_TRUE(!face1_union.Contains(face2_cell));
 
49
}
 
50
 
 
51
static S2Testing::Random& rnd = S2Testing::rnd;
 
52
 
 
53
static void AddCells(S2CellId const& id, bool selected,
 
54
                     vector<S2CellId> *input, vector<S2CellId> *expected) {
 
55
  // Decides whether to add "id" and/or some of its descendants to the
 
56
  // test case.  If "selected" is true, then the region covered by "id"
 
57
  // *must* be added to the test case (either by adding "id" itself, or
 
58
  // some combination of its descendants, or both).  If cell ids are to
 
59
  // the test case "input", then the corresponding expected result after
 
60
  // simplification is added to "expected".
 
61
 
 
62
  if (id == S2CellId::None()) {
 
63
    // Initial call: decide whether to add cell(s) from each face.
 
64
    for (int face = 0; face < 6; ++face) {
 
65
      AddCells(S2CellId::FromFacePosLevel(face, 0, 0), false, input, expected);
 
66
    }
 
67
    return;
 
68
  }
 
69
  if (id.is_leaf()) {
 
70
    // The rnd.OneIn() call below ensures that the parent of a leaf cell
 
71
    // will always be selected (if we make it that far down the hierarchy).
 
72
    DCHECK(selected);
 
73
    input->push_back(id);
 
74
    return;
 
75
  }
 
76
  // The following code ensures that the probability of selecting a cell
 
77
  // at each level is approximately the same, i.e. we test normalization
 
78
  // of cells at all levels.
 
79
  if (!selected && rnd.OneIn(S2CellId::kMaxLevel - id.level())) {
 
80
    // Once a cell has been selected, the expected output is predetermined.
 
81
    // We then make sure that cells are selected that will normalize to
 
82
    // the desired output.
 
83
    expected->push_back(id);
 
84
    selected = true;
 
85
  }
 
86
 
 
87
  // With the rnd.OneIn() constants below, this function adds an average
 
88
  // of 5/6 * (kMaxLevel - level) cells to "input" where "level" is the
 
89
  // level at which the cell was first selected (level 15 on average).
 
90
  // Therefore the average number of input cells in a test case is about
 
91
  // (5/6 * 15 * 6) = 75.  The average number of output cells is about 6.
 
92
 
 
93
  // If a cell is selected, we add it to "input" with probability 5/6.
 
94
  bool added = false;
 
95
  if (selected && !rnd.OneIn(6)) {
 
96
    input->push_back(id);
 
97
    added = true;
 
98
  }
 
99
  int num_children = 0;
 
100
  S2CellId child = id.child_begin();
 
101
  for (int pos = 0; pos < 4; ++pos, child = child.next()) {
 
102
    // If the cell is selected, on average we recurse on 4/12 = 1/3 child.
 
103
    // This intentionally may result in a cell and some of its children
 
104
    // being included in the test case.
 
105
    //
 
106
    // If the cell is not selected, on average we recurse on one child.
 
107
    // We also make sure that we do not recurse on all 4 children, since
 
108
    // then we might include all 4 children in the input case by accident
 
109
    // (in which case the expected output would not be correct).
 
110
    if (rnd.OneIn(selected ? 12 : 4) && num_children < 3) {
 
111
      AddCells(child, selected, input, expected);
 
112
      ++num_children;
 
113
    }
 
114
    // If this cell was selected but the cell itself was not added, we
 
115
    // must ensure that all 4 children (or some combination of their
 
116
    // descendants) are added.
 
117
    if (selected && !added) AddCells(child, selected, input, expected);
 
118
  }
 
119
}
 
120
 
 
121
TEST(S2CellUnion, Normalize) {
 
122
  // Try a bunch of random test cases, and keep track of average
 
123
  // statistics for normalization (to see if they agree with the
 
124
  // analysis above).
 
125
  S2CellUnion cellunion;
 
126
  double in_sum = 0, out_sum = 0;
 
127
  static int const kIters = 2000;
 
128
  for (int i = 0; i < kIters; ++i) {
 
129
    vector<S2CellId> input, expected;
 
130
    AddCells(S2CellId::None(), false, &input, &expected);
 
131
    in_sum += input.size();
 
132
    out_sum += expected.size();
 
133
    cellunion.Init(input);
 
134
    EXPECT_EQ(expected.size(), cellunion.num_cells());
 
135
    for (int i = 0; i < expected.size(); ++i) {
 
136
      EXPECT_EQ(expected[i], cellunion.cell_id(i));
 
137
    }
 
138
 
 
139
    // Test GetCapBound().
 
140
    S2Cap cap = cellunion.GetCapBound();
 
141
    for (int i = 0; i < cellunion.num_cells(); ++i) {
 
142
      EXPECT_TRUE(cap.Contains(S2Cell(cellunion.cell_id(i))));
 
143
    }
 
144
 
 
145
    // Test Contains(S2CellId) and Intersects(S2CellId).
 
146
    for (int j = 0; j < input.size(); ++j) {
 
147
      EXPECT_TRUE(cellunion.Contains(input[j]));
 
148
      EXPECT_TRUE(cellunion.Contains(input[j].ToPoint()));
 
149
      EXPECT_TRUE(cellunion.VirtualContainsPoint(input[j].ToPoint()));
 
150
      EXPECT_TRUE(cellunion.Intersects(input[j]));
 
151
      if (!input[j].is_face()) {
 
152
        EXPECT_TRUE(cellunion.Intersects(input[j].parent()));
 
153
        if (input[j].level() > 1) {
 
154
          EXPECT_TRUE(cellunion.Intersects(input[j].parent().parent()));
 
155
          EXPECT_TRUE(cellunion.Intersects(input[j].parent(0)));
 
156
        }
 
157
      }
 
158
      if (!input[j].is_leaf()) {
 
159
        EXPECT_TRUE(cellunion.Contains(input[j].child_begin()));
 
160
        EXPECT_TRUE(cellunion.Intersects(input[j].child_begin()));
 
161
        EXPECT_TRUE(cellunion.Contains(input[j].child_end().prev()));
 
162
        EXPECT_TRUE(cellunion.Intersects(input[j].child_end().prev()));
 
163
        EXPECT_TRUE(cellunion.Contains(
 
164
                        input[j].child_begin(S2CellId::kMaxLevel)));
 
165
        EXPECT_TRUE(cellunion.Intersects(
 
166
                        input[j].child_begin(S2CellId::kMaxLevel)));
 
167
      }
 
168
    }
 
169
    for (int j = 0; j < expected.size(); ++j) {
 
170
      if (!expected[j].is_face()) {
 
171
        EXPECT_TRUE(!cellunion.Contains(expected[j].parent()));
 
172
        EXPECT_TRUE(!cellunion.Contains(expected[j].parent(0)));
 
173
      }
 
174
    }
 
175
 
 
176
    // Test Contains(S2CellUnion*), Intersects(S2CellUnion*),
 
177
    // GetUnion(), GetIntersection(), and GetDifference().
 
178
    vector<S2CellId> x, y, x_or_y, x_and_y;
 
179
    for (int j = 0; j < input.size(); ++j) {
 
180
      bool in_x = rnd.OneIn(2);
 
181
      bool in_y = rnd.OneIn(2);
 
182
      if (in_x) x.push_back(input[j]);
 
183
      if (in_y) y.push_back(input[j]);
 
184
      if (in_x || in_y) x_or_y.push_back(input[j]);
 
185
    }
 
186
    S2CellUnion xcells, ycells, x_or_y_expected, x_and_y_expected;
 
187
    xcells.Init(x);
 
188
    ycells.Init(y);
 
189
    x_or_y_expected.Init(x_or_y);
 
190
 
 
191
    S2CellUnion x_or_y_cells;
 
192
    x_or_y_cells.GetUnion(&xcells, &ycells);
 
193
    EXPECT_TRUE(x_or_y_cells == x_or_y_expected);
 
194
 
 
195
    // Compute the intersection of "x" with each cell of "y",
 
196
    // check that this intersection is correct, and append the
 
197
    // results to x_and_y_expected.
 
198
    for (int j = 0; j < ycells.num_cells(); ++j) {
 
199
      S2CellId yid = ycells.cell_id(j);
 
200
      S2CellUnion u;
 
201
      u.GetIntersection(&xcells, yid);
 
202
      for (int k = 0; k < xcells.num_cells(); ++k) {
 
203
        S2CellId xid = xcells.cell_id(k);
 
204
        if (xid.contains(yid)) {
 
205
          EXPECT_TRUE(u.num_cells() == 1 && u.cell_id(0) == yid);
 
206
        } else if (yid.contains(xid)) {
 
207
          EXPECT_TRUE(u.Contains(xid));
 
208
        }
 
209
      }
 
210
      for (int k = 0; k < u.num_cells(); ++k) {
 
211
        EXPECT_TRUE(xcells.Contains(u.cell_id(k)));
 
212
        EXPECT_TRUE(yid.contains(u.cell_id(k)));
 
213
      }
 
214
      x_and_y.insert(x_and_y.end(), u.cell_ids().begin(), u.cell_ids().end());
 
215
    }
 
216
    x_and_y_expected.Init(x_and_y);
 
217
 
 
218
    S2CellUnion x_and_y_cells;
 
219
    x_and_y_cells.GetIntersection(&xcells, &ycells);
 
220
    EXPECT_TRUE(x_and_y_cells == x_and_y_expected);
 
221
 
 
222
    S2CellUnion x_minus_y_cells, y_minus_x_cells;
 
223
    x_minus_y_cells.GetDifference(&xcells, &ycells);
 
224
    y_minus_x_cells.GetDifference(&ycells, &xcells);
 
225
    EXPECT_TRUE(xcells.Contains(&x_minus_y_cells));
 
226
    EXPECT_TRUE(!x_minus_y_cells.Intersects(&ycells));
 
227
    EXPECT_TRUE(ycells.Contains(&y_minus_x_cells));
 
228
    EXPECT_TRUE(!y_minus_x_cells.Intersects(&xcells));
 
229
    EXPECT_TRUE(!x_minus_y_cells.Intersects(&y_minus_x_cells));
 
230
    S2CellUnion diff_union;
 
231
    diff_union.GetUnion(&x_minus_y_cells, &y_minus_x_cells);
 
232
    S2CellUnion diff_intersection_union;
 
233
    diff_intersection_union.GetUnion(&diff_union, &x_and_y_cells);
 
234
    EXPECT_TRUE(diff_intersection_union == x_or_y_cells);
 
235
 
 
236
    vector<S2CellId> test, dummy;
 
237
    AddCells(S2CellId::None(), false, &test, &dummy);
 
238
    for (int j = 0; j < test.size(); ++j) {
 
239
      bool contains = false, intersects = false;
 
240
      for (int k = 0; k < expected.size(); ++k) {
 
241
        if (expected[k].contains(test[j])) contains = true;
 
242
        if (expected[k].intersects(test[j])) intersects = true;
 
243
      }
 
244
      EXPECT_EQ(contains, cellunion.Contains(test[j]));
 
245
      EXPECT_EQ(intersects, cellunion.Intersects(test[j]));
 
246
    }
 
247
 
 
248
  }
 
249
  printf("avg in %.2f, avg out %.2f\n", in_sum / kIters, out_sum / kIters);
 
250
}
 
251
 
 
252
static double GetMaxAngle(S2CellUnion const& covering, S2Point const& axis) {
 
253
  double max_angle = 0;
 
254
  for (int i = 0; i < covering.num_cells(); ++i) {
 
255
    S2Cell cell(covering.cell_id(i));
 
256
    S2Cap cell_cap = cell.GetCapBound();
 
257
    double angle = axis.Angle(cell_cap.axis()) + cell_cap.angle().radians();
 
258
    max_angle = max(max_angle, angle);
 
259
  }
 
260
  return max_angle;
 
261
}
 
262
 
 
263
TEST(S2CellUnion, Expand) {
 
264
  // This test generates coverings for caps of random sizes, and expands
 
265
  // the coverings by a random radius, and then make sure that the new
 
266
  // covering covers the expanded cap.  It also makes sure that the
 
267
  // new covering is not too much larger than expected.
 
268
 
 
269
  S2RegionCoverer coverer;
 
270
  for (int i = 0; i < 1000; ++i) {
 
271
    S2Cap cap = S2Testing::GetRandomCap(
 
272
        S2Cell::AverageArea(S2CellId::kMaxLevel), 4 * M_PI);
 
273
 
 
274
    // Expand the cap by a random factor whose log is uniformly distributed
 
275
    // between 0 and log(1e2).
 
276
    S2Cap expanded_cap = S2Cap::FromAxisHeight(
 
277
        cap.axis(), min(2.0, pow(1e2, rnd.RandDouble()) * cap.height()));
 
278
 
 
279
    double radius = expanded_cap.angle().radians() - cap.angle().radians();
 
280
    int max_level_diff = rnd.Uniform(8);
 
281
 
 
282
    S2CellUnion covering;
 
283
    coverer.set_max_cells(1 + rnd.Skewed(10));
 
284
    coverer.GetCellUnion(cap, &covering);
 
285
    S2Testing::CheckCovering(cap, covering, true);
 
286
 
 
287
    double max_angle = GetMaxAngle(covering, cap.axis());
 
288
    int min_level = S2CellId::kMaxLevel;
 
289
    for (int i = 0; i < covering.num_cells(); ++i) {
 
290
      min_level = min(min_level, covering.cell_id(i).level());
 
291
    }
 
292
    covering.Expand(S1Angle::Radians(radius), max_level_diff);
 
293
    S2Testing::CheckCovering(expanded_cap, covering, false);
 
294
 
 
295
    int expand_level = min(min_level + max_level_diff,
 
296
                           S2::kMinWidth.GetMaxLevel(radius));
 
297
    double expanded_max_angle = GetMaxAngle(covering, cap.axis());
 
298
 
 
299
    // If the covering includes a tiny cell along the boundary, in theory the
 
300
    // maximum angle of the covering from the cap axis can increase by up to
 
301
    // twice the maximum length of a cell diagonal.  We allow for an increase
 
302
    // of slightly more than this because cell bounding caps are not exact.
 
303
    EXPECT_LE(expanded_max_angle - max_angle,
 
304
              2.02 * S2::kMaxDiag.GetValue(expand_level));
 
305
    // TODO(user): This fails for some random seeds,
 
306
    // e.g. initialize the random seed to 3 in s2testing.cc.  This
 
307
    // means the assumption above is incorrect and needs to be
 
308
    // revisited.
 
309
  }
 
310
}
 
311
 
 
312
static void TestInitFromRange(S2CellId const& min_id,
 
313
                              S2CellId const& max_id) {
 
314
  S2CellUnion cell_union;
 
315
  cell_union.InitFromRange(min_id, max_id);
 
316
  vector<S2CellId> const& cell_ids = cell_union.cell_ids();
 
317
 
 
318
  EXPECT_GT(cell_ids.size(), 0);
 
319
  EXPECT_EQ(min_id, cell_ids.front().range_min());
 
320
  EXPECT_EQ(max_id, cell_ids.back().range_max());
 
321
  for (int i = 1; i < cell_ids.size(); ++i) {
 
322
    EXPECT_EQ(cell_ids[i].range_min(), cell_ids[i-1].range_max().next());
 
323
  }
 
324
  EXPECT_FALSE(cell_union.Normalize());
 
325
}
 
326
 
 
327
TEST(S2CellUnion, InitFromRange) {
 
328
  // Check the very first leaf cell and face cell.
 
329
  S2CellId face1_id = S2CellId::FromFacePosLevel(0, 0, 0);
 
330
  TestInitFromRange(face1_id.range_min(), face1_id.range_min());
 
331
  TestInitFromRange(face1_id.range_min(), face1_id.range_max());
 
332
 
 
333
  // Check the very last leaf cell and face cell.
 
334
  S2CellId face5_id = S2CellId::FromFacePosLevel(5, 0, 0);
 
335
  TestInitFromRange(face1_id.range_min(), face1_id.range_max());
 
336
  TestInitFromRange(face1_id.range_max(), face1_id.range_max());
 
337
 
 
338
  // Check random ranges of leaf cells.
 
339
  for (int i = 0; i < 100; ++i) {
 
340
    S2CellId x = S2Testing::GetRandomCellId(S2CellId::kMaxLevel);
 
341
    S2CellId y = S2Testing::GetRandomCellId(S2CellId::kMaxLevel);
 
342
    if (x > y) swap(x, y);
 
343
    TestInitFromRange(x, y);
 
344
  }
 
345
}
 
346
 
 
347
TEST(S2CellUnion, Empty) {
 
348
  S2CellUnion empty_cell_union;
 
349
  S2CellId face1_id = S2CellId::FromFacePosLevel(1, 0, 0);
 
350
 
 
351
  // Normalize()
 
352
  empty_cell_union.Normalize();
 
353
  EXPECT_EQ(0, empty_cell_union.num_cells());
 
354
 
 
355
  // Denormalize(...)
 
356
  vector<S2CellId> output;
 
357
  empty_cell_union.Denormalize(0, 2, &output);
 
358
  EXPECT_EQ(0, empty_cell_union.num_cells());
 
359
 
 
360
  // Pack(...)
 
361
  empty_cell_union.Pack();
 
362
 
 
363
  // Contains(...)
 
364
  EXPECT_FALSE(empty_cell_union.Contains(face1_id));
 
365
  EXPECT_TRUE(empty_cell_union.Contains(&empty_cell_union));
 
366
 
 
367
  // Intersects(...)
 
368
  EXPECT_FALSE(empty_cell_union.Intersects(face1_id));
 
369
  EXPECT_FALSE(empty_cell_union.Intersects(&empty_cell_union));
 
370
 
 
371
  // GetUnion(...)
 
372
  S2CellUnion cell_union;
 
373
  cell_union.GetUnion(&empty_cell_union, &empty_cell_union);
 
374
  EXPECT_EQ(0, cell_union.num_cells());
 
375
 
 
376
  // GetIntersection(...)
 
377
  S2CellUnion intersection;
 
378
  intersection.GetIntersection(&empty_cell_union, face1_id);
 
379
  EXPECT_EQ(0, intersection.num_cells());
 
380
  intersection.GetIntersection(&empty_cell_union, &empty_cell_union);
 
381
  EXPECT_EQ(0, intersection.num_cells());
 
382
 
 
383
  // GetDifference(...)
 
384
  S2CellUnion difference;
 
385
  difference.GetDifference(&empty_cell_union, &empty_cell_union);
 
386
  EXPECT_EQ(0, difference.num_cells());
 
387
 
 
388
  // Expand(...)
 
389
  empty_cell_union.Expand(S1Angle::Radians(1), 20);
 
390
  EXPECT_EQ(0, empty_cell_union.num_cells());
 
391
  empty_cell_union.Expand(10);
 
392
  EXPECT_EQ(0, empty_cell_union.num_cells());
 
393
}
 
394
 
 
395
TEST(S2CellUnion, Detach) {
 
396
  S2CellId face1_id = S2CellId::FromFacePosLevel(1, 0, 0);
 
397
  S2CellUnion face1_union;
 
398
  vector<S2CellId> ids;
 
399
  ids.push_back(face1_id);
 
400
  face1_union.Init(ids);
 
401
  ASSERT_EQ(1, face1_union.num_cells());
 
402
  EXPECT_EQ(face1_id, face1_union.cell_id(0));
 
403
 
 
404
  vector<S2CellId> retrieve;
 
405
  retrieve.push_back(S2CellId::Sentinel());
 
406
  face1_union.Detach(&retrieve);
 
407
  ASSERT_EQ(1, retrieve.size());
 
408
  EXPECT_EQ(face1_id, retrieve[0]);
 
409
  EXPECT_EQ(0, face1_union.num_cells());
 
410
}
 
411
 
 
412
TEST(S2CellUnion, LeafCellsCovered) {
 
413
  S2CellUnion cell_union;
 
414
 
 
415
  // empty union
 
416
  EXPECT_EQ(0, cell_union.LeafCellsCovered());
 
417
 
 
418
 
 
419
  vector<S2CellId> ids;
 
420
  ids.push_back(S2CellId::FromFacePosLevel(
 
421
      0, (1ULL << ((S2CellId::kMaxLevel << 1) - 1)), S2CellId::kMaxLevel));
 
422
  // One leaf on face 0.
 
423
  cell_union.Init(ids);
 
424
  EXPECT_EQ(1ULL, cell_union.LeafCellsCovered());
 
425
 
 
426
  // Face 0.
 
427
  ids.push_back(S2CellId::FromFacePosLevel(0, 0, 0));
 
428
  cell_union.Init(ids);
 
429
  EXPECT_EQ(1ULL << 60, cell_union.LeafCellsCovered());
 
430
  // Five faces.
 
431
  cell_union.Expand(0);
 
432
  EXPECT_EQ(5ULL << 60, cell_union.LeafCellsCovered());
 
433
  // Whole world.
 
434
  cell_union.Expand(0);
 
435
  EXPECT_EQ(6ULL << 60, cell_union.LeafCellsCovered());
 
436
 
 
437
  // Add some disjoint cells.
 
438
  ids.push_back(S2CellId::FromFacePosLevel(1, 0, 1));
 
439
  ids.push_back(S2CellId::FromFacePosLevel(2, 0, 2));
 
440
  ids.push_back(S2CellId::FromFacePosLevel(2, (1ULL << 60), 2));
 
441
  ids.push_back(S2CellId::FromFacePosLevel(3, 0, 14));
 
442
  ids.push_back(S2CellId::FromFacePosLevel(4, (1ULL << 60), 15));
 
443
  ids.push_back(S2CellId::FromFacePosLevel(4, 0, 27));
 
444
  ids.push_back(S2CellId::FromFacePosLevel(5, 0, 30));
 
445
  cell_union.Init(ids);
 
446
  uint64 expected = 1ULL + (1ULL << 6) + (1ULL << 30) + (1ULL << 32) +
 
447
      (2ULL << 56) + (1ULL << 58) + (1ULL << 60);
 
448
  EXPECT_EQ(expected, cell_union.LeafCellsCovered());
 
449
}