Fix cell_to_parent so it creates correct parent cells

[eblade]

The current implementation of cell_to_parent has a small bug in, easiest demonstrated by this example:

>>> quadbin.cell_to_parent(5203557525705719807, 2)
5199053926078349311
>>> quadbin.cell_to_tile(5199053926078349311)
(2, 1, 2)
>>> quadbin.tile_to_cell((2, 1, 2))
5199124294822526975
>>> quadbin.cell_to_tile(5199124294822526975)
(2, 1, 2)

Note that the produced parent cell, while giving the correct tile, when turned into a cell again, does not have the same cell number, which would be expected.

The function in question:

def cell_to_parent(cell, parent_resolution):
    """Compute the parent cell for a specific resolution.

    Parameters
    ----------
    cell : int
    parent_resolution : int

    Returns
    -------
    int

    Raises
    ------
    ValueError
        If the parent resolution is not valid.
    """
    resolution = get_resolution(cell)

    if parent_resolution < 0 or parent_resolution > resolution:
        raise ValueError("Invalid resolution")

    return (
        (cell & ~(0x1F << 52))
        | (parent_resolution << 52)
        | (FOOTER >> (parent_resolution << 2))
    )

The bug is the last line, where parent_resolution should only be shifted once. This can be seen in your js implementation for instance (though here it is *2 instead of <<1):

export function cellToParent(quadbin: Quadbin): Quadbin {
  const zparent = getResolution(quadbin) - 1n;
  const parent =
    (quadbin & ~(0x1fn << 52n)) | (zparent << 52n) | (0xfffffffffffffn >> (zparent * 2n));
  return parent;
}

Also your SQL does it this way:

CREATE OR REPLACE FUNCTION @@PG_SCHEMA@@.QUADBIN_TOPARENT(
    quadbin BIGINT,
    resolution INT
)
RETURNS BIGINT
AS
$BODY$
  SELECT CASE
  WHEN resolution < 0 OR resolution > ((quadbin >> 52) & 31)
  THEN @@PG_SCHEMA@@.__CARTO_ERROR('Invalid resolution')::BIGINT
  ELSE
    (quadbin & ~(31::BIGINT << 52)) | (resolution::BIGINT << 52) | (4503599627370495 >> (resolution << 1))
  END;
$BODY$
LANGUAGE sql IMMUTABLE PARALLEL SAFE;

This changes allows for the reversibility of the cell.

I also fixed the test and created an additional one for this specific purpose.

Thanks! // Johan

[luipir]

@eblade tnx for the contribution... none of us is in place these days due to holidays, we'll do a review next week I suppose.

[eblade]

Thanks @Jesus89 !

Sounds great! It was not my intention to make that package file part of the pull request, just wanted to build a personal package to use meanwhile and did not realize it was applied to the PR.

[Jesus89]

I've updated python versions in ci: https://github.com/CartoDB/quadbin-py/pull/15

[Jesus89]

Patch version released: https://pypi.org/project/quadbin/0.2.1

Thanks for your contribution!