# 13 Feb 2022, 18:28

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)));
}

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();

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.