zOrder for DDB for geospatial

zOrder.ts

// UTILS

export const getPaddingFromPrecision = (
  floatingPointPrecision: number,
): number => {
  return Math.ceil(Math.log2(360 * floatingPointPrecision));
};

export const convertToBinary = (
  num: number,
  floatingPointPrecision: number,
): string => {
  const roundedNum = Math.round((num + 180.0) * floatingPointPrecision);

  const coordinatePadding = getPaddingFromPrecision(floatingPointPrecision);

  return roundedNum.toString(2).padStart(coordinatePadding, '0');
};

export const interleaveBytes = (a: string, b: string): string => {
  const result: string[] = [];

  for (let i = 0; i < a.length; i++) {
    result.push(a[i] ?? '');
    result.push(b[i] ?? '');
  }

  return result.join('');
};

export const buildZAddress = (
  lat: number,
  lon: number,
  floatingPointPrecision: number,
): string => {
  const latBinary = convertToBinary(lat, floatingPointPrecision);
  const lonBinary = convertToBinary(lon, floatingPointPrecision);

  return interleaveBytes(latBinary, lonBinary);
};
export const parseZAddressToLatLong = (
  zAddress: string,
  floatingPointPrecision: number,
): [number, number] => {
  const latBinary = zAddress
    .split('')
    .filter((_, i) => i % 2 === 0)
    .join('');
  const lonBinary = zAddress
    .split('')
    .filter((_, i) => i % 2 === 1)
    .join('');

  const lat = parseInt(latBinary, 2) / floatingPointPrecision - 180.0;
  const lon = parseInt(lonBinary, 2) / floatingPointPrecision - 180.0;

  return [lat, lon];
};

export const convertZAddress = (
  zAddress: string,
  toPadding: number,
  padWith: '0' | '1' = '0',
): string => {
  const zAddressLength = zAddress.length;

  if (zAddressLength > 2 * toPadding) {
    return zAddress.slice(0, 2 * toPadding);
  }

  return zAddress.padEnd(2 * toPadding, padWith);
};


const decimalPlaces = 3;
export const floatingPointPrecision = 10 ** decimalPlaces;

const coordinatePadding = getPaddingFromPrecision(floatingPointPrecision);

const TIMESTAMP_SIZE = 36;
const timestampHexSize = Math.ceil(TIMESTAMP_SIZE / 4);
const zIndexHexSize = Math.ceil(coordinatePadding / 2);

export const deserialize = (
  bin: Uint8Array,
): {
  zIndex: string;
  date: Date;
} => {
  const buf = Buffer.from(bin);

  const zIndex = parseInt(buf.toString('hex').slice(0, -timestampHexSize), 16)
    .toString(2)
    .padStart(2 * coordinatePadding, '0');

  const date = new Date(
    parseInt(buf.toString('hex').slice(-timestampHexSize), 16) * 1000,
  );

  return { zIndex, date };
};

export const serialize = ({
  zIndex,
  date,
}: {
  zIndex: string;
  date: Date;
}): Uint8Array => {
  const payload = parseInt(zIndex, 2)
    .toString(16)
    .padStart(zIndexHexSize, '0')
    .concat(
      Math.floor(date.getTime() / 1000)
        .toString(16)
        .padStart(timestampHexSize, '0'),
    );

  const buf = Buffer.from(
    payload.length % 2 === 0 ? payload : '0'.concat(payload),
    'hex',
  );

  return buf;
};

// CORE Function, bad naming 🤭

export const absoluteBanger = (decimalPlaces: number, stepsOutside: number) => {
  const floatingPointPrecision = 10 ** decimalPlaces;
  const coordinatePadding = getPaddingFromPrecision(floatingPointPrecision);
  const isRelevant = (
    minZAddress: string,
    maxZAddress: string,
    zAddress: string,
  ) => {
    const [minLat, minLon] = parseZAddressToLatLong(
      minZAddress,
      floatingPointPrecision,
    );
    const [maxLat, maxLon] = parseZAddressToLatLong(
      maxZAddress,
      floatingPointPrecision,
    );
    const [lat, lon] = parseZAddressToLatLong(zAddress, floatingPointPrecision);

    return lat >= minLat && lat <= maxLat && lon >= minLon && lon <= maxLon;
  };

  const zDivide = (minZAddress: string, maxZAddress: string) => {
    const mostSignificantBit = getMostSignificantBit(minZAddress, maxZAddress);

    switch (mostSignificantBit % 2) {
      case 0:
        return zDivideHorizontal(minZAddress, maxZAddress, mostSignificantBit);
      case 1:
        return zDivideVertical(minZAddress, maxZAddress, mostSignificantBit);
      default:
        throw new Error('Something went wrong');
    }
  };

  const getMostSignificantBit = (minZAddress: string, maxZAddress: string) => {
    for (
      let mostSignificantBit = 0;
      mostSignificantBit < minZAddress.length;
      mostSignificantBit++
    ) {
      if (minZAddress[mostSignificantBit] !== maxZAddress[mostSignificantBit]) {
        return mostSignificantBit;
      }
    }

    return -1;
  };

  const zDivideHorizontal = (
    minZAddress: string,
    maxZAddress: string,
    mostSignificantBit: number,
  ): [string, string] => {
    const [, minLon] = parseZAddressToLatLong(
      minZAddress,
      floatingPointPrecision,
    );
    const [, maxLon] = parseZAddressToLatLong(
      maxZAddress,
      floatingPointPrecision,
    );
    const litMaxLon = maxLon;
    const bigMinLon = minLon;

    const latBinaryStart = minZAddress
      .split('')
      .slice(0, mostSignificantBit)
      .filter((_, i) => i % 2 === 0)
      .join('');

    const litMaxLatBinary = latBinaryStart
      .concat('0')
      .padEnd(coordinatePadding, '1');
    const bigMinLatBinary = latBinaryStart
      .concat('1')
      .padEnd(coordinatePadding, '0');

    const litMax = interleaveBytes(
      litMaxLatBinary,
      convertToBinary(litMaxLon, floatingPointPrecision),
    );
    const bigMin = interleaveBytes(
      bigMinLatBinary,
      convertToBinary(bigMinLon, floatingPointPrecision),
    );

    return [litMax, bigMin];
  };

  const zDivideVertical = (
    minZAddress: string,
    maxZAddress: string,
    mostSignificantBit: number,
  ): [string, string] => {
    const [minLat] = parseZAddressToLatLong(
      minZAddress,
      floatingPointPrecision,
    );
    const [maxLat] = parseZAddressToLatLong(
      maxZAddress,
      floatingPointPrecision,
    );
    const litMaxLat = maxLat;
    const bigMinLat = minLat;

    const lonBinaryStart = minZAddress
      .split('')
      .slice(0, mostSignificantBit)
      .filter((_, i) => i % 2 === 1)
      .join('');

    const litMaxLonBinary = lonBinaryStart
      .concat('0')
      .padEnd(coordinatePadding, '1');
    const bigMinLonBinary = lonBinaryStart
      .concat('1')
      .padEnd(coordinatePadding, '0');

    const litMax = interleaveBytes(
      convertToBinary(litMaxLat, floatingPointPrecision),
      litMaxLonBinary,
    );
    const bigMin = interleaveBytes(
      convertToBinary(bigMinLat, floatingPointPrecision),
      bigMinLonBinary,
    );

    return [litMax, bigMin];
  };

  const incrementZAddress = (zAddress: string) => {
    const binaryZAddressString = '0b' + zAddress;

    const bigBinary = BigInt(binaryZAddressString);
    const biggerBinary = bigBinary + BigInt(1);

    return biggerBinary.toString(2).padStart(2 * coordinatePadding, '0');
  };

  const recursiveBanger = (
    zMin: string,
    zMax: string,
    recursionCount = 0,
    zCurrent = zMin,
    missCount = 0,
  ): [string, string][] => {
    if (zCurrent >= zMax) {
      return [[zMin, zMax]];
    }

    let nextMissCount = missCount;
    let nextZAddress = zCurrent;
    while (nextMissCount < stepsOutside) {
      nextMissCount = isRelevant(zMin, zMax, nextZAddress)
        ? 0
        : nextMissCount + 1;
      nextZAddress = incrementZAddress(nextZAddress);

      if (nextZAddress === zMax) {
        return [[zMin, zMax]];
      }
    }

    const [litMax, bigMin] = zDivide(zMin, zMax);

    return recursiveBanger(
      zMin,
      litMax,
      recursionCount + 1,
      zCurrent,
      missCount,
    ).concat(recursiveBanger(bigMin, zMax, recursionCount + 1));
  };

  return { floatingPointPrecision, recursiveBanger };
};

// DynamoDB Query

const queryItems = async (
  recursiveBanger: (zMin: string, zMax: string) => [string, string][],
  smallPrecision: number,
  searchBox: readonly [[number, number], [number, number]],
) => {
  const smallPadding = getPaddingFromPrecision(smallPrecision);
  const startTime = new Date();

  const [[latMin, longMin], [latMax, longMax]] = searchBox;

  const zmin = buildZAddress(latMin, longMin, bigPrecision);
  const zmax = buildZAddress(latMax, longMax, bigPrecision);

  const queries = recursiveBanger(
    convertZAddress(zmin, smallPadding),
    convertZAddress(zmax, smallPadding),
  ).map<[string, string]>(([zStart, zEnd]) => [
    convertZAddress(zStart, bigPadding, '0'),
    convertZAddress(zEnd, bigPadding, '1'),
  ]);

  const computeTime = new Date().getTime() - startTime.getTime();

  let totalCapacityUnit = 0;
  const results = await Promise.all(
    queries.map(async query => {
      const [queryZmin, queryZmax] = query;
      const command = new QueryCommand({
        TableName: 'myTable',
        KeyConditionExpression: 'PK = :PK AND SK BETWEEN :zmin AND :zmax',
        ExpressionAttributeValues: {
          ':PK': Buffer.from('Covid'),
          ':zmin': serialize({
            zIndex: queryZmin,
            date: new Date(0),
          }),
          ':zmax': serialize({
            zIndex: queryZmax,
            date: new Date(),
          }),
        },
        ReturnConsumedCapacity: 'TOTAL',
      });

      const { Items = [], ConsumedCapacity } = await dbDocClient.send(command);

      if (ConsumedCapacity) {
        totalCapacityUnit += ConsumedCapacity.CapacityUnits ?? 0;
      }

      return Items;
    }),
  );

  const result = results.flat();

  const itemsInsideTheBox = result.filter(({ latitude, longitude }) => {
    return (
      parseFloat(latitude) >= latMin &&
      parseFloat(latitude) <= latMax &&
      parseFloat(longitude) >= longMin &&
      parseFloat(longitude) <= longMax
    );
  });
};