{"id":790,"date":"2014-01-08T20:52:38","date_gmt":"2014-01-08T19:52:38","guid":{"rendered":"https:\/\/thoughtflow.dk\/?p=790"},"modified":"2018-11-24T08:58:36","modified_gmt":"2018-11-24T07:58:36","slug":"open-sourcing-the-past","status":"publish","type":"post","link":"https:\/\/davidlebech.com\/thoughtflow\/open-sourcing-the-past\/","title":{"rendered":"Open-sourcing the past"},"content":{"rendered":"<p>While studying at the University of Oregon, I worked as a teaching assistant in three different computer science courses. One of them was <a href=\"http:\/\/www.cs.uoregon.edu\/Classes\/10W\/cis323\/\" title=\"CIS 323 course homepage\" target=\"_blank\">CIS 323 Data Structures Lab<\/a> but this course was a bit special because it had its own course number and I was teaching it almost on my own.<\/p>\n<p><em>It was quite a roller coaster ride<\/em>&#8230; <span id='easy-footnote-1-790' class='easy-footnote-margin-adjust'><\/span><span class='easy-footnote'><a href='https:\/\/davidlebech.com\/thoughtflow\/open-sourcing-the-past\/#easy-footnote-bottom-1-790' title='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.'><sup>1<\/sup><\/a><\/span><\/p>\n<p>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 <a href=\"http:\/\/en.wikipedia.org\/wiki\/Left-leaning_red%E2%80%93black_tree\" title=\"Left-leaning red-black tree -- Wikipedia\" target=\"_blank\">left-leaning red-black tree<\/a> (LLRB), invented by <a href=\"http:\/\/www.cs.princeton.edu\/~rs\/\" title=\"Robert Sedgewick\" target=\"_blank\">Robert Sedgewick<\/a> in 2008. Back in the beginning of 2010, I could not find any publicly available C++ implementation of the LLRB tree <span id='easy-footnote-2-790' class='easy-footnote-margin-adjust'><\/span><span class='easy-footnote'><a href='https:\/\/davidlebech.com\/thoughtflow\/open-sourcing-the-past\/#easy-footnote-bottom-2-790' title='The reference implementation was written in Java'><sup>2<\/sup><\/a><\/span> 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.<\/p>\n<p>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, <a href=\"https:\/\/github.com\/dlebech\/data-structures-cpp\" title=\"Data structures in C++ on Github\" target=\"_blank\">here is the code<\/a> 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.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[114],"tags":[115,117,116,45],"class_list":["post-790","post","type-post","status-publish","format-standard","hentry","category-code","tag-c","tag-code-2","tag-data-structures","tag-programming"],"_links":{"self":[{"href":"https:\/\/davidlebech.com\/thoughtflow\/wp-json\/wp\/v2\/posts\/790","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/davidlebech.com\/thoughtflow\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/davidlebech.com\/thoughtflow\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/davidlebech.com\/thoughtflow\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/davidlebech.com\/thoughtflow\/wp-json\/wp\/v2\/comments?post=790"}],"version-history":[{"count":0,"href":"https:\/\/davidlebech.com\/thoughtflow\/wp-json\/wp\/v2\/posts\/790\/revisions"}],"wp:attachment":[{"href":"https:\/\/davidlebech.com\/thoughtflow\/wp-json\/wp\/v2\/media?parent=790"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/davidlebech.com\/thoughtflow\/wp-json\/wp\/v2\/categories?post=790"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/davidlebech.com\/thoughtflow\/wp-json\/wp\/v2\/tags?post=790"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}