competitive-scala

My personal repertoire of datastructures and utilities written in pure Scala.

• All implementations are pure, with the exception of randomized algorithms which rely on an impure random number generator oracle.
• All implementations are asymptotically optimal up to a log^k(n) factor. Most of the time the chosen algorithm is indeed optimal, however the operations on the underlying immutable datastructures may require additional time (compared to their impure counterpart), thus the log factor.
• All implementations are self-contained: no external libraries are used and files are isolated from each other.

Repertoire

Geometry

• Point in polygon

Graphs

• Maximum bipartite matching (unweighted)
• Minimum spanning tree (undirected)
• Shortest path
  • Single source, positive weights, optional early stopping (Dijkstra)
  • Single source, negative weights and negative loop detection (Bellman-Ford)
• Topological sort
• Union-find data structure

Number theory

• Combinatorics
  • Count combinations and permutations
• Fast Fourier transform (FFT)
  • Transformation and its inverse
  • Convolution
• Matrix arithmetic
  • Dimensions, identity and rotations
  • Multiplication and element-wise operations
  • Gaussian elimination and inverse
• Modular arithmetic
  • GCD and LCM
  • Modular inverse, Bézout identity and Chinese remainder
  • Fast exponentiation, sum of powers
  • Randomized Miller-Rabin primality test
  • Discrete logarithm
• Rational arithmetic

Arrays, sequences and strings

• Arithmetic expression parser (shunting-yard)
• JSON parser (recursive)
• Run-length encoding/decoding
• String searching
  • Longest prefix also a suffix
  • Knuth-Morris-Pratt (KMP) search
  • Palindrome search
• Suffixes
  • Suffix array
  • Burrows-Wheeler transform and its inverse
  • Rotation array
  • Longest common prefix (LCP) array

Other utilities

• Binary search
  • Binary search and its four variants
• Cartesian coordinates
  • Points and vectors
  • Axis-aligned bounding boxes (AABB)
• Fixed point and orbit
• Hexagonal grid
• Memoization
• Rhombic dodecahedral grid
• Roman numerals from/to integer
• SAT solving (DPLL)
• Space filling curves
  • Binary index curve
  • Gray code curve
  • Hilbert curve
• State