TileKey.h

/*
 * Copyright (C) 2019-2023 HERE Europe B.V.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * SPDX-License-Identifier: Apache-2.0
 * License-Filename: LICENSE
 */
 
#pragma once
 
#include <bitset>
#include <cstdint>
#include <string>
 
#include <olp/core/CoreApi.h>
#include <olp/core/porting/optional.h>
 
namespace olp {
namespace geo {
 
class CORE_API TileKey {
 public:
  enum { LevelCount = 32 };
  enum { MaxLevel = LevelCount - 1 };
 
  enum class TileKeyQuadrant : uint8_t { SW, SE, NW, NE, Invalid };
 
  constexpr TileKey() : row_(0), column_(0), level_(LevelCount) {}
 
  constexpr TileKey(const TileKey&) = default;
 
  TileKey& operator=(const TileKey&) = default;
 
  constexpr bool IsValid() const {
    return level_ < LevelCount && row_ < (1u << level_) &&
           column_ < (1u << level_);
  }
 
  constexpr bool operator==(const TileKey& other) const {
    return level_ == other.level_ && row_ == other.row_ &&
           column_ == other.column_;
  }
 
  constexpr bool operator!=(const TileKey& other) const {
    return !operator==(other);
  }
 
  constexpr bool operator<(const TileKey& other) const {
    return level_ != other.level_
               ? level_ < other.level_
               : row_ != other.row_ ? row_ < other.row_
                                    : column_ < other.column_;
  }
 
  std::string ToQuadKey() const;
 
  static TileKey FromQuadKey(const std::string& quad_key);
 
  std::string ToHereTile() const;
 
  static TileKey FromHereTile(const std::string& key);
 
  std::uint64_t ToQuadKey64() const;
 
  static TileKey FromQuadKey64(std::uint64_t quad_key);
 
  static TileKey FromRowColumnLevel(std::uint32_t row, std::uint32_t column,
                                    std::uint32_t level);
 
  constexpr std::uint32_t Level() const { return level_; }
 
  constexpr std::uint32_t Row() const { return row_; }
 
  constexpr std::uint32_t RowCount() const { return 1 << level_; }
 
  constexpr std::uint32_t Column() const { return column_; }
 
  constexpr std::uint32_t ColumnCount() const { return 1 << level_; }
 
  TileKey Parent() const;
 
  bool IsChildOf(const TileKey& tile_key) const;
 
  bool IsParentOf(const TileKey& tile_key) const;
 
  TileKey ChangedLevelBy(int delta) const;
 
  TileKey ChangedLevelTo(std::uint32_t level) const;
 
  std::uint64_t GetSubkey64(int delta) const;
 
  TileKey AddedSubkey64(std::uint64_t sub_quad_key) const;
 
  TileKey AddedSubkey(const std::string& sub_quad_key) const;
 
  TileKey AddedSubHereTile(const std::string& sub_here_tile) const;
 
  constexpr bool HasNextRow() const { return row_ < (1u << level_) - 1; }
 
  TileKey NextRow() const;
 
  constexpr bool HasNextColumn() const { return column_ < (1u << level_) - 1; }
 
  TileKey NextColumn() const;
 
  constexpr bool HasPreviousRow() const { return (row_ > 0); }
 
  TileKey PreviousRow() const;
 
  constexpr bool HasPreviousColumn() const { return (column_ > 0); }
 
  TileKey PreviousColumn() const;
 
  TileKey GetChild(std::uint8_t index) const;
 
  TileKey GetChild(TileKeyQuadrant direction) const;
 
  TileKeyQuadrant RelationshipToParent() const;
 
 private:
  std::uint32_t row_{0};
  std::uint32_t column_{0};
  std::uint32_t level_{LevelCount};
};
 
struct CORE_API QuadKey64Helper {
  explicit constexpr QuadKey64Helper(std::uint64_t key) : key(key) {}
 
  constexpr QuadKey64Helper Parent() const { return QuadKey64Helper{key >> 2}; }
 
  constexpr QuadKey64Helper Child() const { return QuadKey64Helper{key << 2}; }
 
  QuadKey64Helper GetSubkey(int delta) const;
 
  QuadKey64Helper AddedSubkey(QuadKey64Helper sub_key) const;
 
  static inline constexpr std::uint32_t RowsAtLevel(std::uint32_t level) {
    return 1u << level;
  }
 
  static inline constexpr std::uint32_t ChildrenAtLevel(std::uint32_t level) {
    return 1u << (level << 1u);
  }
 
  std::uint64_t key{0};
};
 
using TileKeyLevels = std::bitset<TileKey::LevelCount>;
 
CORE_API porting::optional<std::uint32_t> GetMinTileKeyLevel(
    const TileKeyLevels& levels);
 
CORE_API porting::optional<std::uint32_t> GetMaxTileKeyLevel(
    const TileKeyLevels& levels);
 
CORE_API porting::optional<std::uint32_t> GetNearestAvailableTileKeyLevel(
    const TileKeyLevels& levels, const std::uint32_t reference_level);
 
CORE_API std::ostream& operator<<(std::ostream& out,
                                  const geo::TileKey& tile_key);
 
}  // namespace geo
}  // namespace olp
 
namespace std {
 
template <>
struct hash<olp::geo::TileKey> {
  std::size_t operator()(const olp::geo::TileKey& tile_key) const {
    return std::hash<std::uint64_t>()(tile_key.ToQuadKey64());
  }
};
 
}  // namespace std