Peter Goldsborough goldsborough

🔨

Fixing things

Fix the world

goldsborough / random_for_random.cpp

Created October 19, 2015 10:23

Generate a random value in one range given a function to generate a uniformly-random number from another range.

	std::size_t random_for_random(const std::pair<std::size_t, std::size_t>& base_range,
	const std::function<std::size_t(void)>& base_function,
	const std::pair<std::size_t, std::size_t>& target_range)
	{
	// The number of values in the base range
	const std::size_t base_size = base_range.second - base_range.first + 1;

	// The number of values in the target range
	const std::size_t target_size = target_range.second - target_range.first + 1;

goldsborough / include_v8.cpp

Created October 21, 2015 22:16

Include a JavaScript file in Google V8.

	void include(const v8::FunctionCallbackInfo<v8::Value>& file)
	{
	auto isolate = file.GetIsolate();

	if (file.Length() != 1)
	{
	auto message = v8::String::NewFromUtf8(isolate,
	"Invalid number "
	"of arguments!");
	v8::Exception::SyntaxError(message);

goldsborough / longest_subsequence.cpp

Created October 23, 2015 21:51

Find the longest increasing subsequence in N^2 time using dynamic programming.

	template<typename Container>
	class LongestSubsequence
	{
	public:

	using size_t = unsigned int;

	using cache_t = std::unordered_map<size_t, size_t>;

	LongestSubsequence(const Container& container)

goldsborough / dictionary.cpp

Created October 23, 2015 22:47

Yet another hashmap :)

	template<typename Key, typename Value>
	class Dictionary
	{
	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 / shortest-distance.cpp

Created October 24, 2015 21:56

Find the shortest distance between two words in string, optimized for many queries.

	class Lookup
	{
	public:

	using size_t = std::size_t;

	Lookup(const std::string& words)
	{
	reset(words);
	}

goldsborough / partition.cpp

Created October 24, 2015 22:27

Hopefully finally edge-case-secure partitioning algorithm.

	template<typename Iterator>
	Iterator partition(Iterator begin, Iterator end)
	{
	auto pivot = begin++;

	if (pivot == end \|\| begin == end) return pivot;

	for (--end; begin != end; ++begin)
	{
	while (begin != end && begin < pivot) ++begin;

goldsborough / n-smallest.cpp

Created October 24, 2015 22:28

Quick-select algorithm to find the n-smallest elements.

	template<typename Iterator>
	Iterator part(Iterator begin, Iterator end)
	{
	auto pivot = begin++;

	if (pivot == begin \|\| begin == end) return pivot;

	for (--end; begin != end; ++begin)
	{
	while (begin != end && begin < pivot) ++begin;

goldsborough / n-largest-heap.cpp

Created October 24, 2015 23:22

Heap implementation to keep track of the largest N values in a stream.

	template<typename T, std::size_t N>
	class NLargestHeap
	{
	public:

	using size_t = std::size_t;

	static const size_t minimum_capacity = 10;

	NLargestHeap(std::initializer_list<T> list,

goldsborough / longest_made_of_others.cpp

Created October 25, 2015 00:23

Find the longest word in a list made of other words in that list.

	template<typename Iterator>
	class LongestOfOthers
	{
	public:

	using T = typename std::iterator_traits<Iterator>::value_type;

	Iterator operator()(Iterator begin, Iterator end)
	{
	if (begin == end) return end;

goldsborough / median_keeper.cpp

Created October 25, 2015 01:17

A class to keep the median of an incoming stream of values.