Open-sourcing the past

While studying at the University of Oregon, I worked as a teaching assistant in three different computer science courses. One of them was CIS 323 Data Structures Lab but this course was a bit special because it had its own course number and I was teaching it almost on my own.

It was quite a roller coaster ride… ¹

Anyway, throughout the course, we implemented some classic and often used data structures and algorithms in various forms. In my opinion, the most notable data structure we implemented was a fairly new balanced tree data structure called the left-leaning red-black tree (LLRB), invented by Robert Sedgewick in 2008. Back in the beginning of 2010, I could not find any publicly available C++ implementation of the LLRB tree ² which made it fun to use in class because it was very new. This means that there is a possibility that my implementation was the first-ever implementation of the LLRB tree in C++. It is a fun thought but it is not very significant, considering it is only a few lines of code, the delete operation was not implemented and it was never released. Until now.

I recently went through some old course material and found the code. So I emailed the University of Oregon and the course supervisor and with their permission, here is the code which I might expand with a few more data structures once I have looked through the material. I have refactored the code from the original but it still has the mark of a C++ beginner. It was fun going through it again though.

1. The course used C++ so the students could get a feel for something else than Java. I could probably have used something else but I stuck to the syllabus from previous years. Unfortunately, I had never written a line of C++ code before, I had never designed an assignment before, I had never performed a lecture before and I had never spoken to an audience of 50 people before. It was scary as hell. I had bits and pieces of assignments from previous years but in the end, I had to change the syllabus slightly and write quite a bit of C++ from scratch.
2. The reference implementation was written in Java