Peter Goldsborough goldsborough

🔨

Fixing things

Fix the world

goldsborough / sorted_insert.cpp

Created October 15, 2015 23:16

Insert a sorted range into another sorted range, better solution.

	template<typename Iterator1, typename Iterator2>
	void sorted_insert(Iterator1 first_begin,
	Iterator1 first_end,
	Iterator2 second_begin,
	Iterator2 second_end,
	Iterator2 buffer_end)
	{
	--first_begin;
	--first_end;
	--second_end;

goldsborough / get_max.cpp

Created October 16, 2015 21:59

Determine the greater of two values without using comparison operators.

	template<typename T>
	constexpr bool is_positive(const T& value)
	{
	return ! (value & 1 << (sizeof(T) * 8 - 1));
	}

	template<bool condition>
	struct determine;

	template<>

goldsborough / get_max.cpp

Created October 16, 2015 22:33

Overflow-safe method to determine the greater of two values without comparison operators.

	template<typename T>
	T get_max(const T& first, const T& second)
	{
	double first_half = first / 2.0;
	double second_half = second / 2.0;

	bool sign = std::signbit(first_half - second_half);

	return (sign * second) + (!sign * first);
	}

goldsborough / find_sorting_range.cpp

Created October 17, 2015 19:09

Finds the smallest subsequence that has to be sorted for the entire range to be sorted, in O(N) time.

	template<typename Iterator>
	std::pair<Iterator, Iterator> find_sorting_range(Iterator begin, Iterator end)
	{
	Iterator start_unsorted = begin;

	for (auto previous = start_unsorted++;
	start_unsorted != end;
	++previous, ++start_unsorted)
	{
	if (start_unsorted < previous) break;

goldsborough / maximum_subarray.cpp

Created October 17, 2015 22:46

Super-short algorithm to find the maximum subarray.

	template<typename Iterator>
	auto maximum_subarray(Iterator begin, Iterator end) -> decltype(begin + begin)
	{
	using T = decltype(begin + begin);

	T sum = 0;

	T best = 0;

	auto largest = end;

goldsborough / xml_compression.cpp

Created October 17, 2015 23:47

Compresses XML to a more compact representation.

	template<typename Node>
	class XMLCompressor
	{
	public:

	using map_t = std::map<std::string, std::string>;

	static map_t global_keywords;

	std::string operator()(Node* node, map_t& keywords = global_keywords)

goldsborough / card.cpp

Created October 19, 2015 10:14

Object-oriented representation of a deck of cards.

goldsborough / string_separator.cpp

Created October 19, 2015 10:19

Algorithms to separate a string without whitespace back into constituent words.

	std::vector<std::string> separate(const std::string& string,
	const std::unordered_set<std::string>& dictionary)
	{
	std::vector<std::string> words;

	std::string current;

	for (auto character = string.begin(), end = string.end();
	character != end;
	++character)

goldsborough / tree_to_list.cpp

Created October 19, 2015 10:21

Convert a binary tree to a doubly-linked list.

	template<typename Node>
	class TreeToList
	{
	public:

	Node* operator()(Node* root)
	{
	_transform(root, root);

	while (root->left) root = root->left;

goldsborough / two_sum.cpp

Created October 19, 2015 10:22

Three algorithms for the two-sum problem.

	template<typename Iterator, typename Sum>
	auto find_sum_pairs(Iterator begin, Iterator end, const Sum& target)
	{
	std::vector<std::pair<Iterator, Iterator>> pairs;

	if (begin == end) return pairs;

	// O(N lg N)
	std::sort(begin, end--);