Coordinate Maps and Sets

One problem I was pondering recently is in the geospatial arena - somewhere I spend a lot of my time working. I've noticed that it's relatively easy to do key-value lookups on a single piece of data, i.e. a string or a number. For example, if you want to associate a letter in the alphabet to a score you could use a Map to do something like this:

const map = new Map(["a", 1], ["b", 2], ["c", 3], ["d", 4], ["e", 5], ["f", 6]); //etc

The problem I have been mulling over is if you have a piece of data which is unique but multidemnsional, like a coordinate, how do you handle that? For example this approach now falls apart:

coordinateMap = new Map();
coordinateMap.set([32.95, 83.31], 1);
coordinateMap.set([32.95, 83.31], 2);
coordinateMap.size; // This will return 2, as each array creates it's own entry

Assuming you have a coordinate in the format [number, number], you could simply convert the coordinate to a string using the toString array method. This gives you a unique key for that piece of data:

const coordinateMap = new Map();
const coordinate = [32.95, 83.31];
coordinateMap.set(coordinate.toString(), "some value");

It turns out, the Array toString method is quite slow. However using string concatenation/template strings is quite fast, as fast as using some sort of number pairing function, and as such, we can use something like this:

`${coordinates[0]},${coordinates[1]}`;

Coordinate Map #

This got me thinking, can we come up with a data structure that handles this problem elegantly, with a nice Map-like API? This is where I got to:

import { CoordinateDataStructure } from "./coordinate-data-structure";

export type NotUndefined<T> = T extends undefined ? never : T;

export class CoordinateMap<
  T extends U extends any ? NotUndefined<T> : unknown,
  U = any
> extends CoordinateDataStructure {
  private _size = 0;
  private _map: Map<string, T> = new Map();

  // O(1)
  get size() {
    return this._size;
  }

  // Ignore setting the size property publically
  set size(value: number) {}

  // O(1)
  set(coordinates: [number, number], value: T): void {
    this.validateCoordinate(coordinates);

    if (value === undefined) {
      throw new Error("Values can not be set to undefined - use 'remove'");
    }

    const key = this.getKey(coordinates);

    if (!this._map.get(key)) {
      this._size++;
    }

    this._map.set(key, value);
  }

  // O(1)
  get(coordinates: [number, number]): T | undefined {
    this.validateCoordinate(coordinates);
    const key = this.getKey(coordinates);
    return this._map.get(key);
  }

  // O(1)
  delete(coordinates: [number, number]): void {
    this.validateCoordinate(coordinates);
    const key = this.getKey(coordinates);

    if (this._map.get(key) === undefined) {
      throw new Error(
        `Coordinate [${key}] cannot be removed as is not in CoordinateMap`
      );
    }

    this._size--;
    this._map.delete(key);
  }

  // O(1)
  has(coordinates: [number, number]): boolean {
    this.validateCoordinate(coordinates);
    return this._map.get(this.getKey(coordinates)) !== undefined;
  }

  clear() {
    this._map.clear();
    this._size = 0;
  }
}

Here validateCoordinate and getKey comes from a base abstract class which we share with the Set data structure which is outlined below. For completeness, it looks like so:

export abstract class CoordinateDataStructure {
  protected getKey(coordinates: [number, number]) {
    return `${coordinates[0]},${coordinates[1]}`;
  }

  protected validateCoordinate([lng, lat]: [number, number]) {
    if (
      !(typeof lng === "number" && !isNaN(lng) && lng >= -180 && lng <= 180) ||
      !(typeof lat === "number" && !isNaN(lat) && lat >= -90 && lat <= 90)
    ) {
      throw new Error("Longitude and latitude must be valid");
    }
  }
}

Designing the Map API was a fun little challenge - in the end, I tried to match the classic JavaScript Map API as closely as possible.

To demonstrate, let's say we're in a testing environment like Jest/Mocha etc, here I can demonstrate the API of the class:

const coordinateMap = new CoordinateMap<number>();

expect(coordinateMap.get([0.0, 1.0])).toBe(undefined);
expect(coordinateMap.has([0.0, 1.0])).toBe(false);

coordinateMap.set([0.0, 1.0], 1);

expect(coordinateMap.get([0.0, 1.0])).toBe(1);
expect(coordinateMap.has([0.0, 1.0])).toBe(true);

coordinateMap.delete([0.0, 1.0]);

expect(coordinateMap.get([0.0, 1.0])).toBe(undefined);
expect(coordinateMap.has([0.0, 1.0])).toBe(false);

Coordinate Set #

I also went ahead and implemented an equivalent data structure for the Set data structure:

import { CoordinateDataStructure } from "./coordinate-data-structure";

export class CoordinateSet extends CoordinateDataStructure {
  private _size: number;
  private map: Map<string, [number, number]>;

  constructor(array?: [number, number][]) {
    super();

    if (Array.isArray(array)) {
      this.map = new Map();
      arrOrCoordSet.forEach((c) => {
        this.validateCoordinate(c);
        this.map.set(this.getKey(c), c);
      });
      this._size = arrOrCoordSet.length;
    } else {
      this.map = new Map();
      this._size = 0;
    }
  }

  // O(1)
  get size() {
    return this._size;
  }

  // Ignore setting the size property publically
  set size(value: number) {}

  has(coordinate: [number, number]) {
    return Boolean(this.map.get(this.getKey(coordinate)));
  }

  add(coordinate: [number, number]) {
    const key = this.getKey(coordinate);
    if (this.map.get(key)) {
      return;
    }
    this._size++;
    this.map.set(key, coordinate);
    return this;
  }

  delete(coordinate: [number, number]): boolean {
    const key = this.getKey(coordinate);
    if (!this.map.get(key)) {
      return false;
    }
    this._size--;
    return this.map.delete(key);
  }

  clear() {
    this.map = new Map();
    this._size = 0;
  }
}

This data structure allows you to do the core JavaScript Set operations, like so:

const set = new CoordinateSet();

set.add([180, -90]);
set.add([0.1, 0.2]);
set.delete([180, -90]);
expect(set.size).toBe(1);
set.delete([0.1, 0.2]);
expect(set.size).toBe(0);

A few things could be done to probably improve these data structures, for example adding all the iterable methods such as entries and values. I may extend this at some point and publish it on a library on npm.

Published