GeohashUtils

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You 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.
 */

// NOTE: we keep the header as it came from ASF; it did not originate in Spatial4j

package org.locationtech.spatial4j.io;

import org.locationtech.spatial4j.context.SpatialContext;
import org.locationtech.spatial4j.shape.Point;
import org.locationtech.spatial4j.shape.Rectangle;

import java.util.Arrays;

/**
 * Utilities for encoding and decoding <a href="http://en.wikipedia.org/wiki/Geohash">geohashes</a>.
 * <p>
 * This class isn't used by any other part of Spatial4j; it's included largely for convenience of
 * software using Spatial4j. There are other open-source libraries that have more comprehensive
 * geohash utilities but providing this one avoids an additional dependency for what's a small
 * amount of code.  <em>If you're using Spatial4j just for this class, consider alternatives.</em>
 * <p>
 * This code originally came from <a href="https://issues.apache.org/jira/browse/LUCENE-1512">
 * Apache Lucene, LUCENE-1512</a>.
 */
public class GeohashUtils {

  private static final char[] BASE_32 = {'0', '1', '2', '3', '4', '5', '6',
      '7', '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n',
      'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};//note: this is sorted

  private static final int[] BASE_32_IDX;//sparse array of indexes from '0' to 'z'

  public static final int MAX_PRECISION = 24;//DWS: I forget what level results in needless more precision but it's about this
  private static final int[] BITS = {16, 8, 4, 2, 1};

  static {
    BASE_32_IDX = new int[BASE_32[BASE_32.length-1] - BASE_32[0] + 1];
    assert BASE_32_IDX.length < 100;//reasonable length
    Arrays.fill(BASE_32_IDX,-500);
    for (int i = 0; i < BASE_32.length; i++) {
      BASE_32_IDX[BASE_32[i] - BASE_32[0]] = i;
    }
  }

  private GeohashUtils() {
  }

  /**
   * Encodes the given latitude and longitude into a geohash
   *
   * @param latitude Latitude to encode
   * @param longitude Longitude to encode
   * @return Geohash encoding of the longitude and latitude
   */
  public static String encodeLatLon(double latitude, double longitude) {
    return encodeLatLon(latitude, longitude, 12);
  }

  public static String encodeLatLon(double latitude, double longitude, int precision) {
    double[] latInterval = {-90.0, 90.0};
    double[] lngInterval = {-180.0, 180.0};

    final StringBuilder geohash = new StringBuilder(precision);
    boolean isEven = true;

    int bit = 0;
    int ch = 0;

    while (geohash.length() < precision) {
      double mid = 0.0;
      if (isEven) {
        mid = (lngInterval[0] + lngInterval[1]) / 2D;
        if (longitude > mid) {
          ch |= BITS[bit];
          lngInterval[0] = mid;
        } else {
          lngInterval[1] = mid;
        }
      } else {
        mid = (latInterval[0] + latInterval[1]) / 2D;
        if (latitude > mid) {
          ch |= BITS[bit];
          latInterval[0] = mid;
        } else {
          latInterval[1] = mid;
        }
      }

      isEven = !isEven;

      if (bit < 4) {
        bit++;
      } else {
        geohash.append(BASE_32[ch]);
        bit = 0;
        ch = 0;
      }
    }

    return geohash.toString();
  }

  /**
   * Decodes the given geohash into a longitude (X) and latitude (Y)
   */
  public static Point decode(String geohash, SpatialContext ctx) {
    Rectangle rect = decodeBoundary(geohash,ctx);
    double latitude = (rect.getMinY() + rect.getMaxY()) / 2D;
    double longitude = (rect.getMinX() + rect.getMaxX()) / 2D;
    return ctx.makePoint(longitude,latitude);
	}

  /** Returns min-max lon (X), min-max lat (Y). */
  public static Rectangle decodeBoundary(String geohash, SpatialContext ctx) {
    double minY = -90, maxY = 90, minX = -180, maxX = 180;
    boolean isEven = true;

    for (int i = 0; i < geohash.length(); i++) {
      char c = geohash.charAt(i);
      if (c >= 'A' && c <= 'Z')
        c -= ('A' - 'a');
      final int cd = BASE_32_IDX[c - BASE_32[0]];//TODO check successful?

      for (int mask : BITS) {
        if (isEven) {
          if ((cd & mask) != 0) {
            minX = (minX + maxX) / 2D;
          } else {
            maxX = (minX + maxX) / 2D;
          }
        } else {
          if ((cd & mask) != 0) {
            minY = (minY + maxY) / 2D;
          } else {
            maxY = (minY + maxY) / 2D;
          }
        }
        isEven = !isEven;
      }

    }
    return ctx.makeRectangle(minX, maxX, minY, maxY);
  }

  /** Array of geohashes 1 level below the baseGeohash. Sorted. */
  public static String[] getSubGeohashes(String baseGeohash) {
    String[] hashes = new String[BASE_32.length];
    for (int i = 0; i < BASE_32.length; i++) {//note: already sorted
      char c = BASE_32[i];
      hashes[i] = baseGeohash+c;
    }
    return hashes;
  }

  public static double[] lookupDegreesSizeForHashLen(int hashLen) {
    return new double[]{hashLenToLatHeight[hashLen], hashLenToLonWidth[hashLen]};
  }

  /**
   * Return the shortest geohash length that will have a width &amp; height &gt;= specified arguments.
   */
  public static int lookupHashLenForWidthHeight(double lonErr, double latErr) {
    //loop through hash length arrays from beginning till we find one.
    for(int len = 1; len < MAX_PRECISION; len++) {
      double latHeight = hashLenToLatHeight[len];
      double lonWidth = hashLenToLonWidth[len];
      if (latHeight < latErr && lonWidth < lonErr)
        return len;
    }
    return MAX_PRECISION;
  }

  /** See the table at http://en.wikipedia.org/wiki/Geohash */
  private static final double[] hashLenToLatHeight, hashLenToLonWidth;
  static {
    hashLenToLatHeight = new double[MAX_PRECISION +1];
    hashLenToLonWidth = new double[MAX_PRECISION +1];
    hashLenToLatHeight[0] = 90*2;
    hashLenToLonWidth[0] = 180*2;
    boolean even = false;
    for(int i = 1; i <= MAX_PRECISION; i++) {
      hashLenToLatHeight[i] = hashLenToLatHeight[i-1]/(even?8:4);
      hashLenToLonWidth[i] = hashLenToLonWidth[i-1]/(even?4:8);
      even = ! even;
    }
  }

}