Skip to content

Instantly share code, notes, and snippets.

@zhenghaoz
zhenghaoz / redblacktree.hpp
Last active August 19, 2016 02:53
Red Black Tree
template <typename Key, typename Value>
class RedBlackTree
{
struct Node;
Node *nil = new Node();
Node *root = nil;
// node structure
struct Node {
enum Color { RED, BLACK };
@zhenghaoz
zhenghaoz / skiplist.hpp
Last active August 21, 2016 12:52
Skip List
#include <ctime>
#include <cstdlib>
#include <stack>
#include <memory>
template <class K, class V>
class SkipList
{
// key-value data
struct Pair
@zhenghaoz
zhenghaoz / btree.hpp
Last active February 24, 2018 07:41
B Tree
#include <memory>
#include <vector>
#include <iostream>
template <unsigned N, typename Key, typename Value>
class BTree
{
template <typename T> using vector = std::vector<T>;
template <typename T> using shared_ptr = std::shared_ptr<T>;
@zhenghaoz
zhenghaoz / fibonacciheap.hpp
Created August 22, 2016 01:17
Fibonacci Heap
#include <vector>
#include <cmath>
#include <iostream>
#include <string>
#define D(n) log2(n)
class FibonacciException
{
using string = std::string;
@zhenghaoz
zhenghaoz / vanemdeboas.hpp
Last active May 25, 2022 05:38
van Emde Boas Tree
#include <memory>
#include <vector>
#include <cmath>
#include <iostream>
#define NIL (-1)
#define LOG2(x) ceil(log2(x))
#define SQRT_C(x) (1<<static_cast<int>(ceil(LOG2(x)/2)))
#define SQRT_F(x) (1<<static_cast<int>(floor(LOG2(x)/2)))
#define HIGH(x) (x/SQRT_F(_u))
@zhenghaoz
zhenghaoz / linearprogram.hpp
Last active October 22, 2016 10:55
Linear Programming
#include <vector>
#include <iostream>
#include <algorithm>
#include <limits>
#include <utility>
class StandardForm
{
friend std::ostream &operator<<(std::ostream &out, const StandardForm &standrdform);
friend class SlackForm;
@zhenghaoz
zhenghaoz / fft.hpp
Last active October 22, 2016 10:56
Fast Fourier Transform
#include <complex>
#include <vector>
#include <cmath>
#define COMPLEXE(u) std::complex<double>(cos(u),-sin(u))
int bitwiseReverse(int num, int log2n)
{
int ans = 0;
while (log2n--) {
@zhenghaoz
zhenghaoz / geometry.hpp
Last active June 9, 2018 12:48
Geometry
#include <vector>
#include <algorithm>
#include <iostream>
#include <utility>
#include <cmath>
#include <exception>
// verbose output
/*#define VERBOSE*/
@zhenghaoz
zhenghaoz / re2nfa.cpp
Last active October 24, 2016 08:18
Regexp to NFA(LaTeX)
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <cstdlib>
#include <ctime>
#include <queue>
using namespace std;
@zhenghaoz
zhenghaoz / re2dfa.cpp
Created October 24, 2016 08:19
Regexp to minimal DFA
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <vector>
#include <algorithm>