From 863b4577e42737762141301864ad1d304d400eef Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Konstantin=20Ka=CC=88fer?= Date: Thu, 21 Aug 2014 15:02:08 +0200 Subject: compute unique clip ids per tile, taking covering children into account fixes #206 fixes #220 refs #229 --- include/mbgl/map/source.hpp | 1 + include/mbgl/map/tile.hpp | 12 +- include/mbgl/map/tile_data.hpp | 4 + include/mbgl/util/clip_ids.hpp | 25 +- include/mbgl/util/math.hpp | 4 + src/map/map.cpp | 12 +- src/map/source.cpp | 13 +- src/renderer/painter.cpp | 6 +- src/renderer/painter_clipping.cpp | 8 +- src/util/clip_ids.cpp | 231 ++++++------------ test/clip_ids.cpp | 482 +++++++++++++++++--------------------- 11 files changed, 348 insertions(+), 450 deletions(-) diff --git a/include/mbgl/map/source.hpp b/include/mbgl/map/source.hpp index 4ffd097193..a9ff29e80a 100644 --- a/include/mbgl/map/source.hpp +++ b/include/mbgl/map/source.hpp @@ -36,6 +36,7 @@ public: void finishRender(Painter &painter); std::forward_list getIDs() const; + std::forward_list getLoadedTiles() const; void updateClipIDs(const std::map &mapping); static std::string normalizeSourceURL(const std::string &url, const std::string &access_token); diff --git a/include/mbgl/map/tile.hpp b/include/mbgl/map/tile.hpp index 9cf5ff5341..09462604a7 100644 --- a/include/mbgl/map/tile.hpp +++ b/include/mbgl/map/tile.hpp @@ -18,11 +18,15 @@ namespace mbgl { class TileData; struct ClipID { - explicit ClipID() {} - explicit ClipID(const std::bitset<8> &mask, uint8_t length) : mask(mask), length(length) {} - explicit ClipID(const std::string &mask, uint8_t length) : mask(mask), length(length) {} + inline ClipID() {} + inline ClipID(const std::string &mask_, const std::string &reference_) : mask(mask_), reference(reference_) {} + std::bitset<8> mask; - uint8_t length = 0; + std::bitset<8> reference; + + inline bool operator==(const ClipID &other) const { + return mask == other.mask && reference == other.reference; + } }; class Tile : private util::noncopyable { diff --git a/include/mbgl/map/tile_data.hpp b/include/mbgl/map/tile_data.hpp index 5991613a2d..9bc76727a1 100644 --- a/include/mbgl/map/tile_data.hpp +++ b/include/mbgl/map/tile_data.hpp @@ -49,6 +49,10 @@ public: void reparse(); const std::string toString() const; + inline bool ready() const { + return state == State::parsed; + } + // Override this in the child class. virtual void beforeParse(); virtual void parse() = 0; diff --git a/include/mbgl/util/clip_ids.hpp b/include/mbgl/util/clip_ids.hpp index 748d3d8f5f..52c571d598 100644 --- a/include/mbgl/util/clip_ids.hpp +++ b/include/mbgl/util/clip_ids.hpp @@ -4,15 +4,34 @@ #include #include #include +#include +#include #include namespace mbgl { -static constexpr uint8_t clipMask[9] { 0x00, 0x80, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC, 0xFE, 0xFF }; +class ClipIDGenerator { +private: + struct Leaf { + Leaf(Tile &tile); + void add(const Tile::ID &p); + bool operator==(const Leaf &other) const; -void updateClipIDs(const std::list &array); + Tile &tile; + std::forward_list children; + }; + + typedef std::vector Pool; + std::forward_list pools; + uint8_t bit_offset = 0; + +private: + bool reuseExisting(Leaf &leaf); + +public: + void update(std::forward_list tiles); +}; -std::map computeClipIDs(std::forward_list array); } diff --git a/include/mbgl/util/math.hpp b/include/mbgl/util/math.hpp index fde2a4720b..2bef5b18e2 100644 --- a/include/mbgl/util/math.hpp +++ b/include/mbgl/util/math.hpp @@ -104,6 +104,10 @@ T smoothstep(T edge0, T edge1, T x) { return t * t * (T(3) - T(2) * t); } +// Computes the log2(x) rounded up to the next integer. +// (== number of bits required to store x) +uint32_t ceil_log2(uint64_t x); + } } diff --git a/src/map/map.cpp b/src/map/map.cpp index 6aa9071a4f..d6597565b7 100644 --- a/src/map/map.cpp +++ b/src/map/map.cpp @@ -509,18 +509,12 @@ void Map::updateTiles() { } void Map::updateRenderState() { - std::forward_list ids; - + // Update all clipping IDs. + ClipIDGenerator generator; for (const std::shared_ptr &source : getActiveSources()) { - ids.splice_after(ids.before_begin(), source->source->getIDs()); + generator.update(source->source->getLoadedTiles()); source->source->updateMatrices(painter.projMatrix, state); } - - const std::map clipIDs = computeClipIDs(ids); - - for (const std::shared_ptr &source : getActiveSources()) { - source->source->updateClipIDs(clipIDs); - } } void Map::prepare() { diff --git a/src/map/source.cpp b/src/map/source.cpp index 523a7f3bc7..ecb0be8efa 100644 --- a/src/map/source.cpp +++ b/src/map/source.cpp @@ -102,7 +102,6 @@ void Source::finishRender(Painter &painter) { } } - std::forward_list Source::getIDs() const { std::forward_list ptrs; @@ -113,6 +112,18 @@ std::forward_list Source::getIDs() const { return ptrs; } +std::forward_list Source::getLoadedTiles() const { + std::forward_list ptrs; + auto it = ptrs.before_begin(); + for (const auto &pair : tiles) { + if (pair.second->data->ready()) { + it = ptrs.insert_after(it, pair.second.get()); + } + } + return ptrs; +} + + TileData::State Source::hasTile(const Tile::ID& id) { auto it = tiles.find(id); if (it != tiles.end()) { diff --git a/src/renderer/painter.cpp b/src/renderer/painter.cpp index e813ad24eb..240aff6887 100644 --- a/src/renderer/painter.cpp +++ b/src/renderer/painter.cpp @@ -169,9 +169,9 @@ void Painter::setStrata(float value) { } void Painter::prepareTile(const Tile& tile) { - GLint id = (GLint)tile.clip.mask.to_ulong(); - GLuint mask = clipMask[tile.clip.length]; - glStencilFunc(GL_EQUAL, id, mask); + const GLint ref = (GLint)tile.clip.reference.to_ulong(); + const GLuint mask = (GLuint)tile.clip.mask.to_ulong(); + glStencilFunc(GL_EQUAL, ref, mask); } void Painter::renderTileLayer(const Tile& tile, std::shared_ptr layer_desc, const mat4 &matrix) { diff --git a/src/renderer/painter_clipping.cpp b/src/renderer/painter_clipping.cpp index e94646d922..d8fa3693bd 100644 --- a/src/renderer/painter_clipping.cpp +++ b/src/renderer/painter_clipping.cpp @@ -14,7 +14,6 @@ void Painter::drawClippingMasks(const std::set> &so depthMask(false); glColorMask(false, false, false, false); depthRange(1.0f, 1.0f); - glStencilMask(0xFF); coveringPlainArray.bind(*plainShader, tileStencilBuffer, BUFFER_OFFSET(0)); @@ -31,9 +30,10 @@ void Painter::drawClippingMasks(const std::set> &so void Painter::drawClippingMask(const mat4& matrix, const ClipID &clip) { plainShader->setMatrix(matrix); - GLint id = static_cast(clip.mask.to_ulong()); - GLuint mask = clipMask[clip.length]; - glStencilFunc(GL_ALWAYS, id, mask); + const GLint ref = (GLint)(clip.reference.to_ulong()); + const GLuint mask = (GLuint)(clip.mask.to_ulong()); + glStencilFunc(GL_ALWAYS, ref, mask); + glStencilMask(mask); glDrawArrays(GL_TRIANGLES, 0, (GLsizei)tileStencilBuffer.index()); } diff --git a/src/util/clip_ids.cpp b/src/util/clip_ids.cpp index d815876a06..9e940b3d12 100644 --- a/src/util/clip_ids.cpp +++ b/src/util/clip_ids.cpp @@ -12,187 +12,102 @@ namespace mbgl { -struct TileHierarchy { - TileHierarchy(Tile::ID id, std::list &&children) - : id(id), children(std::move(children)) {} - - const Tile::ID id; - ClipID clip; - std::list children; -}; - -std::list partition(std::forward_list &&array) { - if (array.empty()) { - // We don't have to update the clipping mask because there are no tiles - // anyway. - return {}; +uint32_t ceil_log2(uint64_t x) { + static const uint64_t t[6] = {0xFFFFFFFF00000000, 0x00000000FFFF0000, + 0x000000000000FF00, 0x00000000000000F0, + 0x000000000000000C, 0x0000000000000002}; + uint32_t y = (((x & (x - 1)) == 0) ? 0 : 1); + uint32_t j = 32; + + for (int32_t i = 0; i < 6; i++) { + const uint32_t k = (((x & t[i]) == 0) ? 0 : j); + y += k; + x >>= k; + j >>= 1; } - int8_t minZ = array.begin()->z; - - std::list result; - std::forward_list remainder; - auto remainder_it = remainder.before_begin(); - - while (!array.empty()) { - const Tile::ID id = array.front(); - array.pop_front(); - if (id.z == minZ) { - std::forward_list children; - auto children_it = children.before_begin(); - - array.remove_if([&id, &children, &children_it](const Tile::ID &child) { - if (child.isChildOf(id)) { - children_it = children.insert_after(children_it, child); - return true; - } else { - return false; - } - }); - - result.emplace_back(id, partition(std::move(children))); - } else { - remainder_it = remainder.insert_after(remainder_it, id); - } - } - - // Concatenate the remainder. - if (!remainder.empty()) { - result.splice(result.begin(), partition(std::move(remainder))); - } - - return result; + return y; } -uint8_t prefix(std::list &array, TileHierarchy *parent = nullptr) { - if (array.empty()) { - return 0; - } - - bool all_children_are_immediate = true; - uint8_t max_child_prefix_length = 0; +ClipIDGenerator::Leaf::Leaf(Tile &tile_) : tile(tile_) {} - struct Huffman { - explicit Huffman(int prefix_length, TileHierarchy *item) - : prefix_length(prefix_length), children(1, item) {} - uint8_t prefix_length; - std::vector children; - }; +void ClipIDGenerator::Leaf::add(const Tile::ID &p) { + if (p.isChildOf(tile.id)) { + // Ensure that no already present child is a parent of the new p. + for (const Tile::ID &child : children) { + if (p.isChildOf(child)) + return; + } + children.push_front(p); + } +} - // Create a temporary structure that we use for sorting the prefix tree. - std::list huffman; - std::transform(array.begin(), array.end(), std::back_inserter(huffman), [parent, &all_children_are_immediate, &max_child_prefix_length](TileHierarchy &item) { - uint8_t prefix_length = prefix(item.children, &item); +bool ClipIDGenerator::Leaf::operator==(const Leaf &other) const { + return tile.id == other.tile.id && children == other.children; +} - if (prefix_length > max_child_prefix_length) { - max_child_prefix_length = prefix_length; +bool ClipIDGenerator::reuseExisting(Leaf &leaf) { + for (const std::vector &pool : pools) { + auto existing = std::find(pool.begin(), pool.end(), leaf); + if (existing != pool.end()) { + leaf.tile.clip = existing->tile.clip; + return true; } + } + return false; +} - if (!parent || item.id.z != parent->id.z + 1) { - all_children_are_immediate = false; - } +void ClipIDGenerator::update(std::forward_list tiles) { + Pool pool; - return Huffman { prefix_length + 1, &item }; + tiles.sort([](const Tile *a, const Tile *b) { + return a->id < b->id; }); - while (huffman.size() > 1) { - huffman.sort([](const Huffman &a, const Huffman &b) { - return a.prefix_length < b.prefix_length; - }); - - Huffman &first = *huffman.begin(); - Huffman &second = *(++huffman.begin()); - - assert(&first != &second); - - // Prefix with 0 - std::for_each(first.children.begin(), first.children.end(), [](TileHierarchy *child) { - child->clip.mask >>= 1; - child->clip.mask.set(7, false); // noop - child->clip.length++; - }); - first.prefix_length++; - - // Prefix with 1 - std::for_each(second.children.begin(), second.children.end(), [](TileHierarchy *child) { - child->clip.mask >>= 1; - child->clip.mask.set(7, true); - child->clip.length++; - }); - second.prefix_length++; - - second.children.insert(second.children.end(), first.children.begin(), first.children.end()); - second.prefix_length = first.prefix_length + second.prefix_length; - - // Remove the first child as we've just merged it into the second version. - huffman.erase(huffman.begin()); - } - - uint8_t prefix_length = 0; + const auto end = tiles.end(); + for (auto it = tiles.begin(); it != end; it++) { + if (!*it) { + // Handle null pointers. + continue; + } - // Filter out all-zero bits - bool filter_zero = !all_children_are_immediate || array.size() != 4; + Tile &tile = **it; + Leaf clip { tile }; - for (TileHierarchy &item : array) { - if (filter_zero && !item.clip.mask.any()) { - // Make sure we don't have a prefix that is all zeros. - // item.clip.mask |= (0x80 >> item.length); - item.clip.mask.set(7 - item.clip.length); - item.clip.length++; + // Try to add all remaining ids as children. We sorted the tile list + // by z earlier, so all preceding items cannot be children of the current + // tile. + for (auto child_it = std::next(it); child_it != end; child_it++) { + clip.add((*child_it)->id); } + clip.children.sort(); - if (item.clip.length > prefix_length) { - prefix_length = item.clip.length; + // Loop through all existing pools and try to find a matching ClipID. + if (!reuseExisting(clip)) { + // We haven't found an existing clip ID + pool.push_back(std::move(clip)); } } - return max_child_prefix_length + prefix_length; -} - -void propagate(std::map &mapping, std::list &array, const ClipID &parent = ClipID{}) { - for (auto &item : array) { - item.clip.mask >>= parent.length; - item.clip.mask |= parent.mask; - item.clip.length += parent.length; -#if defined(DEBUG) - auto result = mapping.emplace(item.id, item.clip); - assert("Tried to insert a duplicate item" && result.second == true); -#else - mapping.emplace(item.id, item.clip); -#endif - propagate(mapping, item.children, const_cast(item.clip)); - }; -} - -void updateClipIDs(const std::list &array) { - std::forward_list ids; - std::transform(array.begin(), array.end(), std::front_inserter(ids), [](Tile *item) { - return item->id; - }); - - const std::map mapping = computeClipIDs(ids); + if (pool.size()) { + const uint32_t bit_count = ceil_log2(pool.size() + 1); + const std::bitset<8> mask = uint64_t(((1 << bit_count) - 1) << bit_offset); - std::for_each(array.begin(), array.end(), [&mapping](Tile *item) { - auto it = mapping.find(item->id); - if (it != mapping.end()) { - item->clip = it->second; - } else { - item->clip = ClipID {}; + // We are starting our count with 1 since we need at least 1 bit set to distinguish between + // areas without any tiles whatsoever and the current area. + uint8_t count = 1; + for (Leaf &leaf : pool) { + leaf.tile.clip.mask = mask; + leaf.tile.clip.reference = count++ << bit_offset; } - }); -} -std::map computeClipIDs(std::forward_list array) { - // Sort by zoom level and make sure that we don't have duplicate elements. - array.sort(); - array.unique(); - - std::list hierarchy = partition(std::move(array)); - prefix(hierarchy); + bit_offset += bit_count; + pools.push_front(std::move(pool)); + } - std::map mapping; - propagate(mapping, hierarchy); - return mapping; + if (bit_offset > 8) { + fprintf(stderr, "stencil mask overflow\n"); + } } } diff --git a/test/clip_ids.cpp b/test/clip_ids.cpp index f2e8be98bc..18ef9658e5 100644 --- a/test/clip_ids.cpp +++ b/test/clip_ids.cpp @@ -8,298 +8,244 @@ using namespace mbgl; -TEST(ClipIDs, ClipMasks) { - ASSERT_EQ(0, clipMask[0]); - ASSERT_EQ(0x80, clipMask[1]); - ASSERT_EQ(0xC0, clipMask[2]); - ASSERT_EQ(0xE0, clipMask[3]); - ASSERT_EQ(0xF0, clipMask[4]); - ASSERT_EQ(0xF8, clipMask[5]); - ASSERT_EQ(0xFC, clipMask[6]); - ASSERT_EQ(0xFE, clipMask[7]); - ASSERT_EQ(0xFF, clipMask[8]); +template void generate(const T &sources) { + ClipIDGenerator generator; + + for (size_t j = 0; j < sources.size(); j++) { + std::forward_list tile_ptrs; + std::transform(sources[j].begin(), sources[j].end(), std::front_inserter(tile_ptrs), [](const std::shared_ptr &tile) { return tile.get(); }); + generator.update(tile_ptrs); + } } +template void print(const T &sources) { + for (size_t j = 0; j < sources.size(); j++) { + for (size_t i = 0; i < sources[j].size(); i++) { + std::cout << " ASSERT_EQ(ClipID(\"" << sources[j][i]->clip.mask << "\", \"" << sources[j][i]->clip.reference << "\"), sources[" << j << "][" << i << "]->clip);\n"; + } + } +} TEST(ClipIDs, ParentAndFourChildren) { - std::array, 5> tiles {{ - std::make_unique(Tile::ID { 1, 0, 0 }), // 1/0/0: 11000000 (3) - std::make_unique(Tile::ID { 1, 0, 1 }), // 1/0/1: 11100000 (3) - std::make_unique(Tile::ID { 1, 1, 0 }), // 1/1/0: 10000000 (3) - std::make_unique(Tile::ID { 1, 1, 1 }), // 1/1/1: 10100000 (3) - std::make_unique(Tile::ID { 0, 0, 0 }), // 0/0/0: 10000000 (1) - }}; - - std::list tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[4]->clip.mask); ASSERT_EQ(1, tiles[4]->clip.length); + const std::vector>> sources = { + { + std::make_shared(Tile::ID { 1, 0, 0 }), + std::make_shared(Tile::ID { 1, 0, 1 }), + std::make_shared(Tile::ID { 1, 1, 0 }), + std::make_shared(Tile::ID { 1, 1, 1 }), + std::make_shared(Tile::ID { 0, 0, 0 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][4]->clip); } TEST(ClipIDs, ParentAndFourChildrenNegative) { - std::array, 5> tiles {{ - std::make_unique(Tile::ID { 1, -2, 0 }), // 1/0/0: 11000000 (3) - std::make_unique(Tile::ID { 1, -2, 1 }), // 1/0/1: 11100000 (3) - std::make_unique(Tile::ID { 1, -1, 0 }), // 1/1/0: 10000000 (3) - std::make_unique(Tile::ID { 1, -1, 1 }), // 1/1/1: 10100000 (3) - std::make_unique(Tile::ID { 0, -1, 0 }), // 0/0/0: 10000000 (1) - }}; - - std::list tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[4]->clip.mask); ASSERT_EQ(1, tiles[4]->clip.length); + const std::vector>> sources = { + { + std::make_shared(Tile::ID { 1, -2, 0 }), + std::make_shared(Tile::ID { 1, -2, 1 }), + std::make_shared(Tile::ID { 1, -1, 0 }), + std::make_shared(Tile::ID { 1, -1, 1 }), + std::make_shared(Tile::ID { 0, -1, 0 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][4]->clip); } TEST(ClipIDs, NegativeParentAndMissingLevel) { - std::array, 5> tiles {{ - std::make_unique(Tile::ID { 1, -1, 0 }), // 1/-1/0: 10000000 (1) - std::make_unique(Tile::ID { 2, -1, 0 }), // 2/-1/0: 10000000 (3) - std::make_unique(Tile::ID { 2, -2, 1 }), // 2/-2/1: 11100000 (3) - std::make_unique(Tile::ID { 2, -1, 1 }), // 2/-1/1: 10100000 (3) - std::make_unique(Tile::ID { 2, -2, 0 }), // 2/-2/0: 11000000 (3) - }}; - - std::list tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask); ASSERT_EQ(1, tiles[0]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length); - ASSERT_EQ(std::bitset<8>("11000000"), tiles[4]->clip.mask); ASSERT_EQ(3, tiles[4]->clip.length); + const std::vector>> sources = { + { + std::make_shared(Tile::ID { 1, -1, 0 }), + std::make_shared(Tile::ID { 2, -1, 0 }), + std::make_shared(Tile::ID { 2, -2, 1 }), + std::make_shared(Tile::ID { 2, -1, 1 }), + std::make_shared(Tile::ID { 2, -2, 0 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][4]->clip); } TEST(ClipIDs, SevenOnSameLevel) { - std::array, 7> tiles {{ - std::make_unique(Tile::ID { 2, 0, 0 }), // 2/0/0: 11000000 (3) - std::make_unique(Tile::ID { 2, 0, 1 }), // 2/0/1: 11100000 (3) - std::make_unique(Tile::ID { 2, 0, 2 }), // 2/0/2: 10000000 (3) - std::make_unique(Tile::ID { 2, 1, 0 }), // 2/1/0: 10100000 (3) - std::make_unique(Tile::ID { 2, 1, 1 }), // 2/1/1: 01000000 (3) - std::make_unique(Tile::ID { 2, 1, 2 }), // 2/1/2: 01100000 (3) - std::make_unique(Tile::ID { 2, 2, 0 }), // 2/2/0: 00100000 (3) - }}; - - std::list tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::bitset<8>("11000000"), tiles[0]->clip.mask); ASSERT_EQ(3, tiles[0]->clip.length); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[1]->clip.mask); ASSERT_EQ(3, tiles[1]->clip.length); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); ASSERT_EQ(3, tiles[2]->clip.length); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[3]->clip.mask); ASSERT_EQ(3, tiles[3]->clip.length); - ASSERT_EQ(std::bitset<8>("01000000"), tiles[4]->clip.mask); ASSERT_EQ(3, tiles[4]->clip.length); - ASSERT_EQ(std::bitset<8>("01100000"), tiles[5]->clip.mask); ASSERT_EQ(3, tiles[5]->clip.length); - ASSERT_EQ(std::bitset<8>("00100000"), tiles[6]->clip.mask); ASSERT_EQ(3, tiles[6]->clip.length); + const std::vector>> sources = { + { + std::make_shared(Tile::ID { 2, 0, 0 }), + std::make_shared(Tile::ID { 2, 0, 1 }), + std::make_shared(Tile::ID { 2, 0, 2 }), + std::make_shared(Tile::ID { 2, 1, 0 }), + std::make_shared(Tile::ID { 2, 1, 1 }), + std::make_shared(Tile::ID { 2, 1, 2 }), + std::make_shared(Tile::ID { 2, 2, 0 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00000111", "00000101"), sources[0][4]->clip); + ASSERT_EQ(ClipID("00000111", "00000110"), sources[0][5]->clip); + ASSERT_EQ(ClipID("00000111", "00000111"), sources[0][6]->clip); } TEST(ClipIDs, MultipleLevels) { - std::array, 12> tiles {{ - std::make_unique(Tile::ID { 2, 0, 0 }), // 2/0/0: 10000000 (1) - std::make_unique(Tile::ID { 3, 0, 0 }), // 3/0/0: 10000000 (3) - std::make_unique(Tile::ID { 3, 0, 1 }), // 3/0/1: 11100000 (3) - std::make_unique(Tile::ID { 4, 0, 2 }), // 4/0/2: 11110000 (5) - std::make_unique(Tile::ID { 4, 1, 2 }), // 4/0/3: 11111000 (5) - std::make_unique(Tile::ID { 4, 0, 3 }), // 4/1/2: 11100000 (5) - std::make_unique(Tile::ID { 4, 1, 3 }), // 4/1/3: 11101000 (5) - std::make_unique(Tile::ID { 3, 1, 0 }), // 3/1/0: 10100000 (3) - std::make_unique(Tile::ID { 3, 1, 1 }), // 3/1/1: 11000000 (3) - std::make_unique(Tile::ID { 2, 1, 0 }), // 2/1/0: 01000000 (2) - std::make_unique(Tile::ID { 3, 2, 0 }), // 3/2/0: 01010000 (4) - std::make_unique(Tile::ID { 3, 2, 1 }), // 3/2/1: 01100000 (3) - }}; - - // Use a random order to verify that the result of this algorithm is independent of the - std::random_shuffle(tiles.begin(), tiles.end()); - - std::list tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // Sort them by tile ID so that we know what order we have to test in. - std::sort(tiles.begin(), tiles.end(), [](const std::unique_ptr &a, const std::unique_ptr &b) { - return a->id < b->id; - }); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::string("2/0/0"), std::string(tiles[0]->id)); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask); - ASSERT_EQ(1, tiles[0]->clip.length); - - ASSERT_EQ(std::string("2/1/0"), std::string(tiles[1]->id)); - ASSERT_EQ(std::bitset<8>("01000000"), tiles[1]->clip.mask); - ASSERT_EQ(2, tiles[1]->clip.length); - - ASSERT_EQ(std::string("3/0/0"), std::string(tiles[2]->id)); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[2]->clip.mask); - ASSERT_EQ(3, tiles[2]->clip.length); - - ASSERT_EQ(std::string("3/0/1"), std::string(tiles[3]->id)); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[3]->clip.mask); - ASSERT_EQ(3, tiles[3]->clip.length); - - ASSERT_EQ(std::string("3/1/0"), std::string(tiles[4]->id)); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[4]->clip.mask); - ASSERT_EQ(3, tiles[4]->clip.length); - - ASSERT_EQ(std::string("3/1/1"), std::string(tiles[5]->id)); - ASSERT_EQ(std::bitset<8>("11000000"), tiles[5]->clip.mask); - ASSERT_EQ(3, tiles[5]->clip.length); - - ASSERT_EQ(std::string("3/2/0"), std::string(tiles[6]->id)); - ASSERT_EQ(std::bitset<8>("01010000"), tiles[6]->clip.mask); - ASSERT_EQ(4, tiles[6]->clip.length); - - ASSERT_EQ(std::string("3/2/1"), std::string(tiles[7]->id)); - ASSERT_EQ(std::bitset<8>("01100000"), tiles[7]->clip.mask); - ASSERT_EQ(3, tiles[7]->clip.length); - - ASSERT_EQ(std::string("4/0/2"), std::string(tiles[8]->id)); - ASSERT_EQ(std::bitset<8>("11110000"), tiles[8]->clip.mask); - ASSERT_EQ(5, tiles[8]->clip.length); - - ASSERT_EQ(std::string("4/0/3"), std::string(tiles[9]->id)); - ASSERT_EQ(std::bitset<8>("11111000"), tiles[9]->clip.mask); - ASSERT_EQ(5, tiles[9]->clip.length); - - ASSERT_EQ(std::string("4/1/2"), std::string(tiles[10]->id)); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[10]->clip.mask); - ASSERT_EQ(5, tiles[10]->clip.length); - - ASSERT_EQ(std::string("4/1/3"), std::string(tiles[11]->id)); - ASSERT_EQ(std::bitset<8>("11101000"), tiles[11]->clip.mask); - ASSERT_EQ(5, tiles[11]->clip.length); + const std::vector>> sources = { + { + std::make_shared(Tile::ID { 2, 0, 0 }), + std::make_shared(Tile::ID { 3, 0, 0 }), + std::make_shared(Tile::ID { 3, 0, 1 }), + std::make_shared(Tile::ID { 4, 0, 2 }), + std::make_shared(Tile::ID { 4, 1, 2 }), + std::make_shared(Tile::ID { 4, 0, 3 }), + std::make_shared(Tile::ID { 4, 1, 3 }), + std::make_shared(Tile::ID { 3, 1, 0 }), + std::make_shared(Tile::ID { 3, 1, 1 }), + std::make_shared(Tile::ID { 2, 1, 0 }), + std::make_shared(Tile::ID { 3, 2, 0 }), + std::make_shared(Tile::ID { 3, 2, 1 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00001111", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00001111", "00000011"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00001111", "00000100"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00001111", "00001001"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00001111", "00001011"), sources[0][4]->clip); + ASSERT_EQ(ClipID("00001111", "00001010"), sources[0][5]->clip); + ASSERT_EQ(ClipID("00001111", "00001100"), sources[0][6]->clip); + ASSERT_EQ(ClipID("00001111", "00000101"), sources[0][7]->clip); + ASSERT_EQ(ClipID("00001111", "00000110"), sources[0][8]->clip); + ASSERT_EQ(ClipID("00001111", "00000010"), sources[0][9]->clip); + ASSERT_EQ(ClipID("00001111", "00000111"), sources[0][10]->clip); + ASSERT_EQ(ClipID("00001111", "00001000"), sources[0][11]->clip); } TEST(ClipIDs, Bug206) { - std::array, 11> tiles {{ - std::make_unique(Tile::ID { 10, 162, 395 }), // 10/162/395: 10000000 (3) - std::make_unique(Tile::ID { 10, 162, 396 }), // 10/162/396: 10100000 (3) - std::make_unique(Tile::ID { 10, 163, 395 }), // 10/163/395: 11000000 (2) - std::make_unique(Tile::ID { 11, 326, 791 }), // 11/326/791: 11100000 (4) - std::make_unique(Tile::ID { 12, 654, 1582 }), // 12/654/1582: 11001000 (5) - std::make_unique(Tile::ID { 12, 654, 1583 }), // 12/654/1583: 11010000 (4) - std::make_unique(Tile::ID { 12, 655, 1582 }), // 12/655/1582: 11110000 (5) - std::make_unique(Tile::ID { 12, 655, 1583 }), // 12/655/1583: 11111000 (5) - std::make_unique(Tile::ID { 10, 163, 396 }), // 10/163/396: 01000000 (3) - std::make_unique(Tile::ID { 10, 164, 395 }), // 10/164/395: 01100000 (3) - std::make_unique(Tile::ID { 10, 164, 396 }), // 10/164/396: 00100000 (3) - }}; - - std::list tile_ptrs; - std::transform(tiles.begin(), tiles.end(), std::back_inserter(tile_ptrs), [](std::unique_ptr &tile) { return tile.get(); }); - - updateClipIDs(tile_ptrs); - - // for (const auto &it : tiles) { - // std::cout << std::string(it->id) << ": " << it->clip.mask << " (" << (int)it->clip.length << ")" << std::endl; - // } - - ASSERT_EQ(std::string("10/162/395"), std::string(tiles[0]->id)); - ASSERT_EQ(std::bitset<8>("10000000"), tiles[0]->clip.mask); - ASSERT_EQ(3, tiles[0]->clip.length); - - ASSERT_EQ(std::string("10/162/396"), std::string(tiles[1]->id)); - ASSERT_EQ(std::bitset<8>("10100000"), tiles[1]->clip.mask); - ASSERT_EQ(3, tiles[1]->clip.length); - - ASSERT_EQ(std::string("10/163/395"), std::string(tiles[2]->id)); - ASSERT_EQ(std::bitset<8>("11000000"), tiles[2]->clip.mask); - ASSERT_EQ(2, tiles[2]->clip.length); - - ASSERT_EQ(std::string("11/326/791"), std::string(tiles[3]->id)); - ASSERT_EQ(std::bitset<8>("11100000"), tiles[3]->clip.mask); - ASSERT_EQ(4, tiles[3]->clip.length); - - ASSERT_EQ(std::string("12/654/1582"), std::string(tiles[4]->id)); - ASSERT_EQ(std::bitset<8>("11001000"), tiles[4]->clip.mask); - ASSERT_EQ(5, tiles[4]->clip.length); - - ASSERT_EQ(std::string("12/654/1583"), std::string(tiles[5]->id)); - ASSERT_EQ(std::bitset<8>("11010000"), tiles[5]->clip.mask); - ASSERT_EQ(4, tiles[5]->clip.length); - - ASSERT_EQ(std::string("12/655/1582"), std::string(tiles[6]->id)); - ASSERT_EQ(std::bitset<8>("11110000"), tiles[6]->clip.mask); - ASSERT_EQ(5, tiles[6]->clip.length); - - ASSERT_EQ(std::string("12/655/1583"), std::string(tiles[7]->id)); - ASSERT_EQ(std::bitset<8>("11111000"), tiles[7]->clip.mask); - ASSERT_EQ(5, tiles[7]->clip.length); - - ASSERT_EQ(std::string("10/163/396"), std::string(tiles[8]->id)); - ASSERT_EQ(std::bitset<8>("01000000"), tiles[8]->clip.mask); - ASSERT_EQ(3, tiles[8]->clip.length); - - ASSERT_EQ(std::string("10/164/395"), std::string(tiles[9]->id)); - ASSERT_EQ(std::bitset<8>("01100000"), tiles[9]->clip.mask); - ASSERT_EQ(3, tiles[9]->clip.length); - - ASSERT_EQ(std::string("10/164/396"), std::string(tiles[10]->id)); - ASSERT_EQ(std::bitset<8>("00100000"), tiles[10]->clip.mask); - ASSERT_EQ(3, tiles[10]->clip.length); - + const std::vector>> sources = { + { + std::make_shared(Tile::ID { 10, 162, 395 }), + std::make_shared(Tile::ID { 10, 162, 396 }), + std::make_shared(Tile::ID { 10, 163, 395 }), + std::make_shared(Tile::ID { 11, 326, 791 }), + std::make_shared(Tile::ID { 12, 654, 1582 }), + std::make_shared(Tile::ID { 12, 654, 1583 }), + std::make_shared(Tile::ID { 12, 655, 1582 }), + std::make_shared(Tile::ID { 12, 655, 1583 }), + std::make_shared(Tile::ID { 10, 163, 396 }), + std::make_shared(Tile::ID { 10, 164, 395 }), + std::make_shared(Tile::ID { 10, 164, 396 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00001111", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00001111", "00000010"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00001111", "00000011"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00001111", "00000111"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00001111", "00001000"), sources[0][4]->clip); + ASSERT_EQ(ClipID("00001111", "00001001"), sources[0][5]->clip); + ASSERT_EQ(ClipID("00001111", "00001010"), sources[0][6]->clip); + ASSERT_EQ(ClipID("00001111", "00001011"), sources[0][7]->clip); + ASSERT_EQ(ClipID("00001111", "00000100"), sources[0][8]->clip); + ASSERT_EQ(ClipID("00001111", "00000101"), sources[0][9]->clip); + ASSERT_EQ(ClipID("00001111", "00000110"), sources[0][10]->clip); } -TEST(ClipIDs, DuplicateIDs) { - - std::forward_list tiles {{ - Tile::ID { 2, 0, 0 }, - Tile::ID { 2, 0, 1 }, - Tile::ID { 2, 0, 0 }, - Tile::ID { 2, 0, 1 }, - Tile::ID { 2, 0, 1 }, - }}; - std::map mapping = computeClipIDs(tiles); - - ASSERT_EQ(2ull, mapping.size()); - - // for (const auto &it : mapping) { - // std::cout << std::string(it.first) << "(" << it.first << ")" << ": " << it.second.mask << " (" << (int)it.second.length << ")" << std::endl; - // } +TEST(ClipIDs, MultipleSources) { + const std::vector>> sources = { + { + std::make_shared(Tile::ID { 0, 0, 0 }), + std::make_shared(Tile::ID { 1, 1, 1 }), + std::make_shared(Tile::ID { 2, 2, 1 }), + std::make_shared(Tile::ID { 2, 2, 2 }), + }, + { + std::make_shared(Tile::ID { 0, 0, 0 }), + std::make_shared(Tile::ID { 1, 1, 1 }), + std::make_shared(Tile::ID { 2, 1, 1 }), + std::make_shared(Tile::ID { 2, 2, 2 }), + }, + { + std::make_shared(Tile::ID { 1, 0, 0 }), + std::make_shared(Tile::ID { 1, 0, 1 }), + std::make_shared(Tile::ID { 1, 1, 0 }), + std::make_shared(Tile::ID { 1, 1, 1 }), + std::make_shared(Tile::ID { 2, 1, 1 }), + }, + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000111", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000010"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000111", "00000011"), sources[0][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[0][3]->clip); + ASSERT_EQ(ClipID("00011000", "00001000"), sources[1][0]->clip); + ASSERT_EQ(ClipID("00000111", "00000010"), sources[1][1]->clip); + ASSERT_EQ(ClipID("00011000", "00010000"), sources[1][2]->clip); + ASSERT_EQ(ClipID("00000111", "00000100"), sources[1][3]->clip); + ASSERT_EQ(ClipID("11100000", "00100000"), sources[2][0]->clip); + ASSERT_EQ(ClipID("11100000", "01000000"), sources[2][1]->clip); + ASSERT_EQ(ClipID("11100000", "01100000"), sources[2][2]->clip); + ASSERT_EQ(ClipID("11100000", "10000000"), sources[2][3]->clip); + ASSERT_EQ(ClipID("00011000", "00010000"), sources[2][4]->clip); +} - ASSERT_EQ(std::bitset<8>("01000000"), mapping[Tile::ID(2, 0, 0)].mask); - ASSERT_EQ(2, mapping[Tile::ID(2, 0, 0)].length); - ASSERT_EQ(std::bitset<8>("10000000"), mapping[Tile::ID(2, 0, 1)].mask); - ASSERT_EQ(1, mapping[Tile::ID(2, 0, 1)].length); +TEST(ClipIDs, DuplicateIDs) { + const std::vector>> sources = { + { + std::make_shared(Tile::ID { 2, 0, 0 }), + std::make_shared(Tile::ID { 2, 0, 1 }), + }, + { + std::make_shared(Tile::ID { 2, 0, 0 }), + std::make_shared(Tile::ID { 2, 0, 1 }), + std::make_shared(Tile::ID { 2, 0, 1 }), + } + }; + + generate(sources); + // print(sources); + + ASSERT_EQ(ClipID("00000011", "00000001"), sources[0][0]->clip); + ASSERT_EQ(ClipID("00000011", "00000010"), sources[0][1]->clip); + ASSERT_EQ(ClipID("00000011", "00000001"), sources[1][0]->clip); + ASSERT_EQ(ClipID("00000011", "00000010"), sources[1][1]->clip); + ASSERT_EQ(ClipID("00000011", "00000010"), sources[1][2]->clip); } -- cgit v1.2.1 From 9c5f9218ac0316f2ea6e7d7de6420e967949188b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Konstantin=20Ka=CC=88fer?= Date: Thu, 21 Aug 2014 15:10:01 +0200 Subject: add missing file --- src/util/math.cpp | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) create mode 100644 src/util/math.cpp diff --git a/src/util/math.cpp b/src/util/math.cpp new file mode 100644 index 0000000000..a7eab2d771 --- /dev/null +++ b/src/util/math.cpp @@ -0,0 +1,25 @@ +#include + +namespace mbgl { +namespace util { + +// From http://stackoverflow.com/questions/3272424/compute-fast-log-base-2-ceiling +uint32_t ceil_log2(uint64_t x) { + static const uint64_t t[6] = {0xFFFFFFFF00000000, 0x00000000FFFF0000, + 0x000000000000FF00, 0x00000000000000F0, + 0x000000000000000C, 0x0000000000000002}; + uint32_t y = (((x & (x - 1)) == 0) ? 0 : 1); + uint32_t j = 32; + + for (int32_t i = 0; i < 6; i++) { + const uint32_t k = (((x & t[i]) == 0) ? 0 : j); + y += k; + x >>= k; + j >>= 1; + } + + return y; +} + +} +} \ No newline at end of file -- cgit v1.2.1 From 671e3910d60eefbfefea92820f91114a87ee7252 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Konstantin=20Ka=CC=88fer?= Date: Thu, 21 Aug 2014 15:14:00 +0200 Subject: don't duplicate function --- src/util/clip_ids.cpp | 19 +------------------ 1 file changed, 1 insertion(+), 18 deletions(-) diff --git a/src/util/clip_ids.cpp b/src/util/clip_ids.cpp index 9e940b3d12..9c391c38ad 100644 --- a/src/util/clip_ids.cpp +++ b/src/util/clip_ids.cpp @@ -12,23 +12,6 @@ namespace mbgl { -uint32_t ceil_log2(uint64_t x) { - static const uint64_t t[6] = {0xFFFFFFFF00000000, 0x00000000FFFF0000, - 0x000000000000FF00, 0x00000000000000F0, - 0x000000000000000C, 0x0000000000000002}; - uint32_t y = (((x & (x - 1)) == 0) ? 0 : 1); - uint32_t j = 32; - - for (int32_t i = 0; i < 6; i++) { - const uint32_t k = (((x & t[i]) == 0) ? 0 : j); - y += k; - x >>= k; - j >>= 1; - } - - return y; -} - ClipIDGenerator::Leaf::Leaf(Tile &tile_) : tile(tile_) {} void ClipIDGenerator::Leaf::add(const Tile::ID &p) { @@ -90,7 +73,7 @@ void ClipIDGenerator::update(std::forward_list tiles) { } if (pool.size()) { - const uint32_t bit_count = ceil_log2(pool.size() + 1); + const uint32_t bit_count = util::ceil_log2(pool.size() + 1); const std::bitset<8> mask = uint64_t(((1 << bit_count) - 1) << bit_offset); // We are starting our count with 1 since we need at least 1 bit set to distinguish between -- cgit v1.2.1 From bbd42fe91f238b10416f2323cfb42c422bd2597d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Konstantin=20Ka=CC=88fer?= Date: Thu, 21 Aug 2014 15:34:14 +0200 Subject: don't trip up certain stdlib implementations --- include/mbgl/util/clip_ids.hpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/include/mbgl/util/clip_ids.hpp b/include/mbgl/util/clip_ids.hpp index 52c571d598..5855b16af7 100644 --- a/include/mbgl/util/clip_ids.hpp +++ b/include/mbgl/util/clip_ids.hpp @@ -22,7 +22,7 @@ private: }; typedef std::vector Pool; - std::forward_list pools; + std::forward_list pools; uint8_t bit_offset = 0; private: -- cgit v1.2.1 From 2c6e34a4fe4aa2d0d1a20028e972bfd0dc051cd8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Konstantin=20Ka=CC=88fer?= Date: Thu, 21 Aug 2014 15:39:58 +0200 Subject: add != operator for certain stdlib implementations --- include/mbgl/map/tile.hpp | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/include/mbgl/map/tile.hpp b/include/mbgl/map/tile.hpp index 09462604a7..24845c81a0 100644 --- a/include/mbgl/map/tile.hpp +++ b/include/mbgl/map/tile.hpp @@ -51,6 +51,10 @@ public: return w == rhs.w && z == rhs.z && x == rhs.x && y == rhs.y; } + inline bool operator!=(const ID& rhs) const { + return !operator==(rhs); + } + inline bool operator<(const ID &rhs) const { if (w != rhs.w) return w < rhs.w; if (z != rhs.z) return z < rhs.z; -- cgit v1.2.1