# 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},\${coordinates}`;``

## 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},\${coordinates}`;  }  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