AlgorithmsEdit

Occasionally I’m faced with a programming problem for which I know a particular algorithm is appropriate, and I know that I’ve implemented that algorithm or data structure before. Sometimes though, it can be hard to remember exactly where I did it, but it would be useful to be able to consult my previous work to either reuse it or guide a reimplementation of it.

So, in this article I’m going to provide some links to implementations of various algorithms, data structures, techniques, and utilities that I’ve implemented in open source repos. All links are to concrete commit hashes, to make sure the links never break if files move around, but be aware that iteration may have continued afterwards and that if you want to see the latest, you should check to see whether there were any subsequent changes.

Data structures

• "Poppable" Set in JavaScript (ie. Set which supports "popping" the oldest item).
• "Reversible" Map in JavaScript (ie. Map which remembers intermediate states and can be rolled back).
• "Reversible" Map in TypeScript (ie. Map which remembers intermediate states and can be rolled back).
• Bitwise ring buffer in TypeScript.
• Circular suffix array in TypeScript.
• Condition Tree in TypeScript
• Connection pool in JavaScript.
• Event emitter in TypeScript.
• FIFO queue in TypeScript
• Fast Ruby Array alternative in C (ary.h, ary.c).
• Fast Ruby String alternative in C (str.h, str.c).
• Fast String in C (str.h, str.c).
• Heap (min heap) in C (heap.h/heap.c).
• Heap in TypeScript.
• Immutable Set in TypeScript.
• Interval Tree in TypeScript
• LRU cache in JavaScript.
• Priority queue in TypeScript.
• Red-Black Tree in TypeScript
• Ring buffer in Rust.
• Threadsafe FIFO queue in Objective-C (WOQueue.h, WOQueue.m^[1]).
• Trie in Perl.
• Union-Find in TypeScript.

Basic algoritms

• "Is object" test in TypeScript.
• Clamp value in TypeScript.
• Debounce in TypeScript.
• Dedenter in TypeScript^[2].
• Escape HTML in TypeScript.
• Fisher-Yates shuffle.
• Git’s histogram diff algorithm in Rust.
• Indenter in TypeScript.
• Invariant assertion in TypeScript (emits extra diagnostic info in development build, see also simpler alternative).
• Monte Carlo simulation in TypeScript.
• Mulberry32 fast pseudo-random number generator in TypeScript.
• Myer’s diff algorithm in Rust.
• Numeric base conversion in JavaScript.
• Object mapper in TypeScript (transforms values and keys).
• Permutation using Heap’s method in TypeScript
• RC-4 pseudo-random number generator in JavaScript (note: I didn’t write this one, but I used it).
• Runtime non-nullable assertion in TypeScript.
• Simple function memoizer in JavaScript.
• Stable JSON stringify in TypeScript (consistent output irrespective of insertion order; see also alternative implementation from Relay).
• String hash function (not cryptographic) in JavaScript.
• Strip HTML tags in JavaScript.
• Throttle in TypeScript.
• Topological traversal using depth-first traversal in JavaScript.
• Topological traversal using depth-first traversal in Objective-C.
• UUID v4 generator in ReasonML.
• UUID v4 generator in TypeScript.
• Wilcoxon Signed Rank test in Lua.
• Wilcoxon Signed Rank test in Ruby.
• Wrap text in TypeScript (using the dynamic programming algorithm from TeX).

Parsing

• DFA minimization in TypeScript.
• Dynamic GraphQL lexer in TypeScript.
• Dynamic JSP lexer in JavaScript.
• General purpose dynamic Packrat parser in TypeScript.
• General purpose dynamic lexer in JavaScript.
• General purpose dynamic lexer in TypeScript.
• INI file parser in TypeScript.
• LALR parser generator in TypeScript.
• Lexer generator in TypeScript.
• Lua lexer in Rust (hand-rolled).
• Markdown "frontmatter" parser in TypeScript (see also alternative implementation).
• NFA-to-DFA converter in TypeScript.
• Packrat GraphQL parser in TypeScript.
• Packrat parser generator in Ruby.
• Pratt operator-precedence parsing in Rust.
• Recursive descent parser for Lua in Rust (hand-rolled).
• Regular Expression compiler in TypeScript.
• Regular Expression escaper in TypeScript.
• Regular Expression parser in TypeScript.
• Regular Expression to NFA converter in TypeScript.
• Shell command parser in TypeScript.
• Static GraphQL lexer in TypeScript (this is faster than the dynamic one).
• Static GraphQL parser in TypeScript (this is faster than the Packrat one).
• StringScanner (lexer) in TypeScript^[3].
• TypeScript AST builder.
• TypeScript AST pretty-printer.
• TypeScript AST transformer.
• Vimscript + documentation comment parser in Haskell using Parsec monadic parser combinators.
• Wikitext translator in C (hand-rolled lexer/parser + translator).

Princeton Algorithms course assignments

• 8-puzzle solver using A* search in TypeScript (context: assignment); related:
  • Hamming distance in TypeScript.
  • Manhattan distance in TypeScript.
• Burrows-Wheeler data compression in TypeScript (context: assignment):
  • Burrows-Wheeler transform in TypeScript.
  • Move-to-front encoding in TypeScript.
  • Huffman compression in TypeScript.
• Find collinear points in TypeScript (context: assignment).
• Percolation model in TypeScript (context: assignment).
• Seam carving in TypeScript (context: assignment).
• kd-tree (2d-tree) in TypeScript (context: assignment).

Miscellaneous

• Conway’s Game of Life cellular automaton in JavaScript.
• Escape shell tokens in TypeScript.
• Format Markdown for display in terminal (from "next" project, see also alternative implementation from git-cipher).
• Full-text MySQL search using Ruby.
• Memory barriers in Objective-C.
• Simple string pluralizer in TypeScript.
• Skein hash in TypeScript
• Stochastic optimization via simulated annealing in TypeScript.
• Tag reachability using MySQL and Ruby.
• UTF-16 to UTF-8 converter in TypeScript
• UTF-8 to UTF-32 converter in C.
• Watchman binary protocol in C (watchman.h, watchman.c).

Useful utilities

• "Golden" (snapshot) testing for JavaScript (note that this predates Jest’s own snapshot feature).
• "Golden" (snapshot) testing for Rust (see also macro for checking all shapshots relative to the current package).
• Improved JSON.stringify() in TypeScript (more useful representations of non-primitive types).
• Yarn workspace management scripts.
• Zero-dependency Jest-like testing "framework" in JavaScript.

Appendix: (non-implementation) notes

• Adjacency matrix notes.
• Adjacency list notes.
• Binary Search tree notes.
• Binary tree notes.
• Breadth-first search notes.
• Computing the Maximum Weighted Independent Set of a graph path notes.
• Depth-first search notes.
• Dynamic programming notes.
• Greedy algorithm notes.
• Heap notes.
• Minimum Spanning Tree notes.
• Prim’s Algorithm notes.
• Sparse matrix notes.
• Topological ordering notes.
• Tree rotation notes.
• Tree traversal notes.
• Union-Find notes.

---

1. For now, this repo is private. ↩︎

2. I’ve implemented this code a number of times in different projects. For example, see alternative from Masochist, or from git-cipher, or from dented. ↩︎

3. Alternative implementation from "next" project. ↩︎