compressGeohash.js

/** Geohashes are in base32. */
const MAX_CHILDREN_COUNT = 32

/**
 * Compress an array of Geohashes using Hash Tree compression.
 *
 * @param {string[]} geohashes Array of Geohashes.
 * @param {number} [minChildrenCount=32] The minimum number of children to concider a node full.
 * @returns {string[]} A compressed version of the Geohashes.
 */
export function compressGeohash(
  geohashes,
  minChildrenCount = MAX_CHILDREN_COUNT,
) {
  const hashTree = createHashTree(geohashes, minChildrenCount)
  return createHashes(hashTree)
}

/**
 * @typedef {object} Node A node of the tree.
 * @property {string} code The code of the node (base32 character).
 * @property {boolean} full Whether this node contains all it's children or none (leaf).
 * @property {number} filledChildren
 *   The number of filled children (`children[].full: true`).
 *   We use this to avoid iterating over the children each time.
 * @property {{ [code: string]: Node }} children The children nodes.
 */

/**
 * @typedef {object} HashTree The Hash Tree.
 * @property {{ [code: string]: Node }} children The children nodes.
 */

/**
 * Create a tree from `geohashes`.
 * Each path in the tree correspond to a Geohash.
 *
 * @param {string[]} geohashes Array of Geohashes.
 * @param {number} minChildrenCount The minimum number of children to concider a node full.
 * @returns {HashTree} The root node of the tree.
 */
function createHashTree(geohashes, minChildrenCount) {
  /** @type {HashTree} */
  const hashTree = { children: {} }

  geohashes.forEach(hash => {
    addToTree(hashTree, hash.split(''), minChildrenCount)
  })

  return hashTree
}

/**
 * Add a Geohash path in the given `parent`.
 *
 * @param {HashTree | Node} parent The node in which to add the Geohash path.
 * @param {string[]} path The Geohash path.
 * @param {number} minChildrenCount The minimum number of children to concider a node full.
 * @returns {boolean} Whether the first node of the path is now full.
 */
function addToTree(parent, [code, ...rest], minChildrenCount) {
  const node = parent.children[code] || {
    code,
    full: false,
    filledChildren: 0,
    children: {},
  }

  // Make sure the node is in the tree.
  parent.children[code] = node

  // If the node is already full we don't need to go deeper.
  if (node.full) {
    return false
  }

  // A leaf is always full.
  if (rest.length === 0) {
    node.full = true

    // We might already have children from a previous (longer) hash.
    // We no longer need to keep the children around.
    node.children = {}

    // Notify the parent that this node is now full.
    return true
  }

  if (addToTree(node, rest, minChildrenCount)) {
    // If the child was filled we add it in the counter.
    node.filledChildren += 1

    // When a node has enough filled children it become full.
    if (node.filledChildren === minChildrenCount) {
      node.full = true

      // We might already have children from a previous (longer) hash.
      // We no longer need to keep the children around.
      node.children = {}

      // Notify the parent that this node is now full.
      return true
    }
  }

  return false
}

/**
 * Creates an array of Geohashes from the given Hash Tree.
 *
 * @param {HashTree} hashTree The root node of the tree.
 * @returns {string[]} The array of Geohashes.
 */
function createHashes(hashTree) {
  const geohashes = []

  Object.values(hashTree.children).forEach(node => {
    addToHashes(node, '', geohashes)
  })

  return geohashes
}

/**
 * Add all leaves nodes in the array of Geohashes.
 *
 * @param {Node} node The current node in the tree.
 * @param {string} parentHash The current Geohash of the ancestors.
 * @param {string[]} geohashes The array of Geohashes.
 */
function addToHashes(node, parentHash, geohashes) {
  const hash = `${parentHash}${node.code}`

  // We only add filled node to the result.
  if (node.full) {
    geohashes.push(hash)
  }

  // The node only have children if it isn't filled.
  else {
    Object.values(node.children).forEach(childNode => {
      addToHashes(childNode, hash, geohashes)
    })
  }
}