Skip to content

Instantly share code, notes, and snippets.

View goldsborough's full-sized avatar
🔨
Fixing things

Peter Goldsborough goldsborough

🔨
Fixing things
1k followers · 165 following
View GitHub Profile
@goldsborough
goldsborough / tree_is_balanced.cpp
Created November 8, 2015 23:30
Check is a binary tree is balanced.
template<typename T>
std::pair<bool, std::size_t> _tree_is_balanced(const TreeNode<T>* node)
{
if (! node) return {true, 0};
auto left = _tree_is_balanced(node->left);
if (! left.first) return {false, 0};
auto right = _tree_is_balanced(node->right);
@goldsborough
goldsborough / find_with_empty.cpp
Created November 11, 2015 00:03
Finds a string in a sequence of sorted strings interspersed with empty ones.
template<typename Iterator, typename T>
bool find_with_empty(Iterator begin, Iterator end, const T& value)
{
if (begin == end || value < *begin || value > *std::prev(end))
{
return false;
}
auto middle = begin;
@goldsborough
goldsborough / open-addressing-hash-table.cpp
Created November 11, 2015 14:53
A hash-table using an open-addressing scheme.
template<typename Key, typename Value>
class OpenAddressingHashTable
{
public:
using size_t = std::size_t;
using pre_hash_t = std::function<size_t(const Key&)>;
static const size_t minimum_capacity = 20;
@goldsborough
goldsborough / separate-chaining-hash-table.hpp
Created November 11, 2015 16:03
A hash-table using a separate-chaining scheme.
#ifndef SEPARATE_CHAINING_HASH_TABLE_HPP
#define SEPARATE_CHAINING_HASH_TABLE_HPP
#include <algorithm>
#include <cmath>
#include <functional>
template<typename Key, typename Value>
class SeparateChainingHashTable
{
@goldsborough
goldsborough / red-black-tree.cpp
Created November 11, 2015 19:16
A Red Black Tree.
#ifndef RED_BLACK_TREE_HPP
#define RED_BLACK_TREE_HPP
#include <assert.h>
#include <initializer_list>
#include <stdexcept>
template<typename Key, typename Value>
class RedBlackTree
{
@goldsborough
goldsborough / max_heap.hpp
Created November 11, 2015 20:31
A max-heap.
#ifndef MAX_HEAP_HPP
#define MAX_HEAP_HPP
#include <algorithm>
#include <cstddef>
#include <initializer_list>
#include <stdexcept>
template<typename T>
class MaxHeap
@goldsborough
goldsborough / heap-filter.cpp
Created November 11, 2015 20:32
A heap to keep track of the max N of a stream of values.
#ifndef HEAP_FILTER_HPP
#define HEAP_FILTER_HPP
#include <algorithm>
#include <cstddef>
#include <initializer_list>
#include <stdexcept>
template<typename T>
class HeapFilter
@goldsborough
goldsborough / merge-sort-single-function.hpp
Created November 11, 2015 21:54
Unoptimized single-function versions of merge-sort.
#ifndef MERGE_SORT_SINGLE_FUNCTION_HPP
#define MERGE_SORT_SINGLE_FUNCTION_HPP
#include <assert.h>
#include <algorithm>
#include <iterator>
#include <vector>
template<typename Iterator,
typename T = typename std::iterator_traits<Iterator>::value_type>
@goldsborough
goldsborough / merge-sort.hpp
Created November 11, 2015 21:55
Full optimized version of mergesort.
#ifndef MERGE_SORT_HPP
#define MERGE_SORT_HPP
#include <algorithm>
#include <iterator>
#include <vector>
template<typename Iterator>
class MergeSort
{
@goldsborough
goldsborough / quick-sort.hpp
Created November 11, 2015 21:55
Unoptimized single-function versions of quicksort.
#ifndef QUICK_SORT_SINGLE_FUNCTION_HPP
#define QUICK_SORT_SINGLE_FUNCTION_HPP
#include <iterator>
#include <utility>
template<typename Iterator>
void quick_sort(Iterator begin, Iterator end)
{
if (begin == end || std::next(begin) == end) return;