Left-Leaning Red-Black Tree in F#

tl;dr Wrote a new left-leaning red-black tree. You can reference it from NuGet or download the source from GitHub.

So, I wrote a left-leaning red-black tree library. All this started with Problem 3 from the Advent of Code 2019. The problem has users create 2 wires with multiple segments each, find all intersection points between the two wires, and identify the one closest to the central port. Here’s a visual representation of the problem:

...........
.+-----+...
.|.....|...
.|..+--X-+.
.|..|..|.|.
.|.-X--+.|.
.|..|....|.
.|.......|.
.o-------+.
...........

While there are multiple ways to solve the problem, I figured that such a problem must have already been solved, at least for graphics / game programming. As you can imagine, this is not only true but there has been research into this area for quite a while.

After going down the rabbit-hole of line intersection algorithms (line vs. line segment, Shamos-Hoey algorithm, sweep-line algorithms, etc.), I decided to implement the Bentley-Ottmann algorithm. Bentley-Ottmann seemed approachable and it looked like it could handle all edge cases. Here is the Bentley-Ottmann algorithm in short:

  1. Initialize a priority queue Q of potential future events, each associated with a point in the plane and prioritized by the x-coordinate of the point. So, initially, Q contains an event for each of the endpoints of the input segments.
  2. Initialize a self-balancing binary search tree T of the line segments that cross the sweep line L, ordered by the y-coordinates of the crossing points. Initially, T is empty. (Even though the line sweep L is not explicitly represented, it may be helpful to imagine it as a vertical line which, initially, is at the left of all input segments.)
  3. While Q is nonempty, find and remove the event from Q associated with a point p with minimum x-coordinate. Determine what type of event this is and process it according to the following case analysis:
    1. If p is the left endpoint of a line segment s, insert s into T. Find the line-segments r and t that are respectively immediately above and below s in T (if they exist); if the crossing of r and t (the neighbors of s in the status data structure) forms a potential future event in the event queue, remove this possible future event from the event queue. If s crosses r or t, add those crossing points as potential future events in the event queue.
    2. If p is the right endpoint of a line segment s, remove s from T. Find the segments r and t that (prior to the removal of s) were respectively immediately above and below it in T (if they exist). If r and t cross, add that crossing point as a potential future event in the event queue.
    3. If p is the crossing point of two segments s and t (with s below t to the left of the crossing), swap the positions of s and t in T. After the swap, find the segments r and u (if they exist) that are immediately below and above t and s, respectively. Remove any crossing points rs (i.e. a crossing point between r and s) and tu (i.e. a crossing point between t and u) from the event queue, and, if r and t cross or s and u cross, add those crossing points to the event queue.

Now, as you can tell from the first two steps, we need two primary data structures - a priority queue and self-balancing binary search tree. I was able to find a priority queue fairly easily. However, it wasn’t as easy to find a self-balancing red-black tree. The majority of references I found pointed to one repository (archive) by gradbot, which unfortunately is no longer available.

So, I did what any reasonable developer would do - I decided to write my own.

Search for an existing implementation

I started out by looking at red-black trees. I’ve always enjoyed tree-like data structures due to their inherently ‘recursive’ nature. I started with Wikipedia and quickly found myself on the page for left-leaning red-black trees. Unfortunately, the linked F# implementation was no longer available.

From there, I wandered over to the F# Programming wikibook. I did find a red-black tree implementation there which was very elegant in terms of its balancing function but it did not have a remove function (which is needed for Bentley-Ottmann). I could have written one for it and that would have been the end of it.

However, I was already committed to the path of a left-leaning red-black tree - especially after reading a paper and looking at two separate implementations in Haskell and Elm.

Writing my own

It took a few days to write my own implementation, based heavily on the Elm and Haskell code mentioned earlier. I did try to do a few things though:

  1. I based the API on the F# List and Set modules.
  2. I’ve written a number of tests to ensure the structure is working correctly. This includes property-based tests written using Hedgehog.
  3. I managed to publish a package on NuGet, which I consider a major accomplishment. Just doing this took half as long as writing much of the API.

On the con side, I haven’t used it in a program yet and I haven’t benchmarked it yet. However, I’m definitely planning to do that so that I can put it through its paces (and do my best to stamp out any remaining bugs). If you’d like to use the library yourself, please feel free to reference it in your projects.

See you in the next one!