codelibrary

Collection of algorithms and data structures in C++, Java, Kotlin, Python and Rust

Data structures

• [x] Segment tree c++ java kotlin
• [x] Segment tree without recursion c++ java
• [x] 2d tree c++ java
• [x] Fenwick tree c++ java kotlin rust
• [x] Fenwick tree with extended operations c++ java
• [x] Persistent tree java kotlin rust
• [x] Centroid decomposition c++ java
• [x] Heavy/light decomposition c++ java
• [x] Link/cut tree c++ java
• [x] Link/cut tree for connectivity query java
• [x] Link/cut tree for LCA query java
• [x] Binary heap java
• [x] Binary heap with change priority c++ java
• [x] Disjoint sets c++ java rust
• [x] Treap c++ java kotlin rust
• [x] Treap with indexed key c++ java
• [x] k-d tree for point query c++ java
• [x] k-d tree for rectangular query java
• [x] R-tree java
• [x] Metric tree java
• [x] Quadtree java
• [x] Mergeable heap java rust
• [x] Queue with minimum c++ java
• [x] Sparse table c++ java java
• [x] Sparse segment tree c++
• [x] Wavelet tree c++ java
• [x] Mo’s algorithm java
• [x] Mo’s algorithm with point updates c++

Graph algorithms

• [x] Shortest paths c++ java
• [x] Maximum flow c++ java
• [x] Maximum matching c++ java
• [x] Spanning tree c++ java
• [x] Connectivity c++ java
• [x] Biconnectivity java
• [x] LCA Schieber-Vishkin algorithm c++ java
• [x] LCA java
• [ ] Planarity testing (contribute a link or implementation)
• [ ] Dynamic graph connectivity (contribute a link or implementation)
• [ ] Chu–Liu/Edmonds’ algorithm (contribute a link or implementation)
• [ ] Minimum augmentation to strong connectivity (contribute a link or implementation)
• [ ] Minimum augmentation to biconnectivity (contribute a link or implementation)

String algorithms

• [x] Knuth-Morris-Pratt algorithm c++ java
• [x] Aho-Corasick algorithm c++ java
• [x] Suffix array and lcp array. Radix sort algorithm in O(n*log(n)) c++ java
• [x] Suffix array. Algorithm DC3 in O(n) c++ java
• [x] Suffix array. Algorithm SA-IS in O(n) c++
• [x] Suffix automaton c++ java
• [x] Suffix tree Ukkonen’s algorithm c++ java
• [x] Suffix tree Breslauer-Italiano algorithm c++
• [x] Trie java
• [x] Z-function c++ java
• [x] Hashing c++ java
• [x] Parsing java c++
• [ ] Palindrome tree (contribute a link or implementation)
• [ ] Sorting strings in linear time (contribute a link or implementation)

Sorting algorithms

• [x] Sorting algorithms c++ java
• [x] N-th element java

Geometry algorithms

• [x] Segments intersection c++ java
• [x] Line operations java
• [x] Circle operations java
• [x] Convex hull c++ java
• [x] Point in polygon query c++ java
• [x] Closest pair of points java
• [x] Furthest pair of points c++
• [ ] Implement quaternion (contribute a link or implementation)

Optimization

• [x] Simplex algorithm java

Numerical algorithms

• [x] Fast Fourier transform (FFT) c++ java
• [x] Long arithmetics c++
• [x] Fast subset convolution java
• [x] Fast Walsh-Hadamar transform java
• [x] Karatsuba multiplication java
• [x] Newton interpolation java
• [x] Laguerre’s root-finding algorithm c++

Number theory

• [x] Primes and divisors java c++
• [x] Factorization java c++
• [x] Euclidean algorithm java c++
• [x] Primitive root c++
• [x] Discrete logarithm c++
• [x] Discrete root c++
• [x] Multiplicative function java
• [x] Rational numbers java
• [x] Polynom class c++
• [x] Linear recurrence and Berlekamp-Massey algorithm c++
• [x] Modular operations c++

Combinatorics

• [x] Permutations java
• [x] Combinations java
• [x] Arrangements java
• [x] Partitions java
• [x] Set Partitions java
• [x] Bracket sequences java
• [x] Binomial coefficients java
• [x] Prufer code java

Linear algebra

• [x] Gaussian elimination c++ java kotlin
• [x] Determinant calculation java
• [x] Matrix operations c++ java