Trees
I wanted to remove the duplicates from a collection of points from a web app I was working on.
JavaScript has a Set data structure that you can use instead of an array, but it relies on the identity of the
objects in the collection. For example, if you have something like this:
let points = new Set()
let a = [10, 10]
let b = [10, 10]
points.add(a)
points.add(b)
You wind up with
Set(2) { [ 10, 10 ], [ 10, 10 ] }
And the duplicates aren’t removed. The same is true if you want to use them for keys of a Map. This is not a
problem in Java because you could define a Point class and override hashCode() and equals(), make the
class implement the Hashable protocol, and the duplicates would be handily removed.
Unfortunately, if your points are floating point numbers instead of integers, then comparing for equality is not going to be reliable, and if you have a lot of data, it can take a long time to search for what you’re looking for. What you really want is a tree, in particular, a KdTree.