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 / quicksort.hpp
Created November 11, 2015 21:56
Fully optimized versions of quicksort.
#ifndef QUICK_SORT_HPP
#define QUICK_SORT_HPP
#include <algorithm>
#include <random>
template<typename Iterator>
class QuickSort
{
public:
@goldsborough
goldsborough / trie.hpp
Created November 12, 2015 00:19
A Trie.
#ifndef TRIE_HPP
#define TRIE_HPP
#include <array>
#include <cstddef>
#include <string>
template<typename Value, typename String = std::string, std::size_t N = 128>
class Trie
{
@goldsborough
goldsborough / linked_list_is_palindrome.cpp
Created November 12, 2015 21:27
Checks if a list is a palindrome.
template<typename Node>
bool _is_palindrome(Node* left, Node*& right, bool& move_back)
{
if (left != right)
{
if (! _is_palindrome(left->next, right, move_back)) return false;
}
if (! move_back)
{
@goldsborough
goldsborough / list-graph.hpp
Created November 13, 2015 21:31
Graph & Operations with Adjacency-List representation.
#ifndef LIST_GRAPH_HPP
#define LIST_GRAPH_HPP
#include <cstddef>
#include <queue>
#include <vector>
class ListGraph
{
public:
@goldsborough
goldsborough / matrix-graph.cpp
Last active November 13, 2015 23:11
Graph & Operations for Graphs in Matrix representation.
#ifndef MATRIX_GRAPH_HPP
#define MATRIX_GRAPH_HPP
#include <algorithm>
#include <array>
#include <bitset>
#include <cstddef>
#include <stdexcept>
template<std::size_t V>
@goldsborough
goldsborough / is_binary_palindrome.cpp
Created November 14, 2015 20:31
Checks if an integer is a palindrome in its binary representation.
bool is_binary_palindrome(unsigned int value)
{
unsigned int left = 1 << (sizeof(value) * 8 - 1);
while (!(value & left)) left >>= 1;
for (unsigned int right = 1; left > right; left >>= 1, right <<= 1)
{
bool left_bit = value & left;
bool right_bit = value & right;
@goldsborough
goldsborough / largest_product_of_n.cpp
Created November 15, 2015 02:34
Computes the largest product of N numbers in a of a sequence of N or more numbers.
int largest_product_of_n(std::vector<int> values, std::size_t n)
{
if (values.size() < n)
{
throw std::invalid_argument("Sequence size must at least n!");
}
std::sort(values.begin(), values.end());
int positive_product = 1;
@goldsborough
goldsborough / median-keeper.hpp
Created November 25, 2015 19:55
A class to keep the median of a stream of values.
#ifndef MEDIAN_KEEPER_HPP
#define MEDIAN_KEEPER_HPP
#include <queue>
#include <vector>
template<typename T>
class MedianKeeper
{
public:
@goldsborough
goldsborough / average.cpp
Created December 11, 2015 22:51
A generic averaging function using TMP.
template<typename Accumulator, typename Divisor, std::size_t N>
class Average
{
public:
template<typename... Args>
constexpr auto operator()(Args&&... args)
{
return _average(Accumulator(), std::forward<Args>(args)...);
}
@goldsborough
goldsborough / equal_range_if.cpp
Created December 11, 2015 23:39
Generic TMP lower_bound_if, upper_bound_if and equal_range_if for any predicates and conditions.
template<
typename Iterator,
typename Predicate,
typename Condition
>
Iterator lower_bound_if(Iterator begin,
Iterator end,
Predicate predicate,
Condition condition)
{