geohash.cpp

#include <iostream>
#include <string>
#include <map>
#include <array>
#include <tuple>
#include <iomanip>
#include <algorithm>
#include <cctype>

// Base32 character set used by Geohash
static const std::string BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";

static std::map<char, int> buildBase32Map() {
    std::map<char, int> m;
    for (int i = 0; i < static_cast<int>(BASE32.size()); ++i) {
        m[BASE32[i]] = i;
    }
    return m;
}

static const std::map<char, int> BASE32_MAP = buildBase32Map();

/**
 * Encode latitude/longitude to Geohash string.
 *
 * @param latitude  float between -90 and 90
 * @param longitude float between -180 and 180
 * @param precision number of characters in result (1-12)
 * @return Geohash string
 */
std::string encode(double latitude, double longitude, int precision = 12) {
    std::array<double, 2> latRange = {-90.0, 90.0};
    std::array<double, 2> lngRange = {-180.0, 180.0};

    std::string geohash;
    int bits = 0;
    int bitCount = 0;
    bool isLongitude = true;

    while (static_cast<int>(geohash.size()) < precision) {
        if (isLongitude) {
            double mid = (lngRange[0] + lngRange[1]) / 2.0;
            if (longitude >= mid) {
                bits = (bits << 1) | 1;
                lngRange[0] = mid;
            } else {
                bits = bits << 1;
                lngRange[1] = mid;
            }
        } else {
            double mid = (latRange[0] + latRange[1]) / 2.0;
            if (latitude >= mid) {
                bits = (bits << 1) | 1;
                latRange[0] = mid;
            } else {
                bits = bits << 1;
                latRange[1] = mid;
            }
        }

        isLongitude = !isLongitude;
        ++bitCount;

        // Every 5 bits, append a Base32 character
        if (bitCount == 5) {
            geohash += BASE32[bits];
            bits = 0;
            bitCount = 0;
        }
    }

    return geohash;
}

struct DecodeResult {
    double latitude;
    double longitude;
    double latError;
    double lngError;
};

/**
 * Decode Geohash string to latitude/longitude.
 *
 * @param geohash Geohash string
 * @return DecodeResult with latitude, longitude, and error margins
 */
DecodeResult decode(const std::string& geohash) {
    std::array<double, 2> latRange = {-90.0, 90.0};
    std::array<double, 2> lngRange = {-180.0, 180.0};
    bool isLongitude = true;

    for (char c : geohash) {
        char lower = static_cast<char>(std::tolower(static_cast<unsigned char>(c)));
        int bits = BASE32_MAP.at(lower);

        for (int i = 4; i >= 0; --i) {
            int bit = (bits >> i) & 1;

            if (isLongitude) {
                double mid = (lngRange[0] + lngRange[1]) / 2.0;
                if (bit) {
                    lngRange[0] = mid;
                } else {
                    lngRange[1] = mid;
                }
            } else {
                double mid = (latRange[0] + latRange[1]) / 2.0;
                if (bit) {
                    latRange[0] = mid;
                } else {
                    latRange[1] = mid;
                }
            }

            isLongitude = !isLongitude;
        }
    }

    return {
        (latRange[0] + latRange[1]) / 2.0,
        (lngRange[0] + lngRange[1]) / 2.0,
        (latRange[1] - latRange[0]) / 2.0,
        (lngRange[1] - lngRange[0]) / 2.0
    };
}

/**
 * Get all 8 neighboring Geohash cells.
 *
 * @param geohash Geohash string
 * @return map with keys: n, ne, e, se, s, sw, w, nw
 */
std::map<std::string, std::string> getNeighbors(const std::string& geohash) {
    DecodeResult d = decode(geohash);
    int precision = static_cast<int>(geohash.size());

    // Calculate the step size (2x error = cell size)
    double latStep = d.latError * 2.0;
    double lngStep = d.lngError * 2.0;

    return {
        {"n",  encode(d.latitude + latStep, d.longitude,            precision)},
        {"ne", encode(d.latitude + latStep, d.longitude + lngStep,  precision)},
        {"e",  encode(d.latitude,           d.longitude + lngStep,  precision)},
        {"se", encode(d.latitude - latStep, d.longitude + lngStep,  precision)},
        {"s",  encode(d.latitude - latStep, d.longitude,            precision)},
        {"sw", encode(d.latitude - latStep, d.longitude - lngStep,  precision)},
        {"w",  encode(d.latitude,           d.longitude - lngStep,  precision)},
        {"nw", encode(d.latitude + latStep, d.longitude - lngStep,  precision)},
    };
}

int main() {
    // Encode Eiffel Tower coordinates
    double lat = 48.8584, lng = 2.2945;
    std::string geohash = encode(lat, lng, 8);
    std::cout << "Eiffel Tower Geohash: " << geohash << "\n";

    // Decode back to coordinates
    DecodeResult decoded = decode(geohash);
    std::cout << std::fixed << std::setprecision(4)
              << "Decoded: lat=" << decoded.latitude
              << ", lng=" << decoded.longitude << "\n";

    // Get neighbors
    std::string prefix = geohash.substr(0, 6);
    auto neighbors = getNeighbors(prefix);
    std::cout << "Neighbors of " << prefix << ": {";
    bool first = true;
    for (const auto& [key, value] : neighbors) {
        if (!first) std::cout << ", ";
        std::cout << "'" << key << "': '" << value << "'";
        first = false;
    }
    std::cout << "}\n";

    return 0;
}