Homework #6 – palindrome & compress

compress.hh

#pragma once
#include <cassert>

// compress accepts a forward iterator range [first, last) and an output iterator.
// compress copies the elements from the iterator range to the output iterator
// eliminating all consecutive duplicates.
template <typename ForwardIterator, typename OutputIterator>
void compress(ForwardIterator first, const ForwardIterator last, OutputIterator result)
{
	if (first != last)
	{
		*result = *first;

		while (true)
		{
			bool different = (*first != *(++first));

			if (first == last)
			{
				break;
			}
			else if (different)
			{
				++result;
                                *result = *first;
			}
		}
	}
}

palindrome.hh

#pragma once
#include <cassert>

// palindrome accepts a bidirectional iterator range [first, last) as input and
// returns true if the elements in the range form a palindrome (a sequence that
// reads the same forward and backward) and false otherwise.
template <typename BidirectionalIterator>
bool palindrome(BidirectionalIterator first, BidirectionalIterator last)
{
	if (first == last)
	{
		return false;
	}
	else while (true)
	{
		--last;

		if (*first != *last)
		{
			return false;
		}

		if (first == last)
		{
			return true;
		}

		++first;
	}
}

test.cpp

#include <cassert>
#include <list>
#include <iterator>
#include <algorithm>

#include "palindrome.hh"
#include "compress.hh"

template <typename T>
bool operator==(const std::list<T>& lhs, const std::list<T>& rhs)
{
	return std::equal(lhs.begin(), lhs.end(), rhs.begin());
}


void test_palindrome()
{
	typedef std::list<int> list;

	// a. An empty std::list
	{
		const list data;
		assert(palindrome(data.begin(), data.end()) == false);
	}

	// b. A non-empty std::list containing an odd number of elements that form a palindrome
	{
		const list data{1};
		assert(palindrome(data.begin(), data.end()) == true);
	}

	// c. A non-empty std::list containing an even number of elements that form a palindrome
	{
		const list data{ 1, 2, 3, 4, 4, 3, 2, 1 };
		assert(palindrome(data.begin(), data.end()) == true);
	}


	// d. A non-empty std::list containing an odd number of elements that form a non-palindrome
	{
		const list data{ 1, 2, 3, 4, 5 };
		assert(palindrome(data.begin(), data.end()) == false);
	}

	// e. A non-empty std::list containing an even number of elements that form a non-palindrome
	{
		const list data{ 1, 2 };
		assert(palindrome(data.begin(), data.end()) == false);
	}

	// 1. First example
	{
		const list data{ 1, 2, 3, 4, 3, 2, 1 };
		assert(palindrome(data.begin(), data.end()) == true);
	}

	// 2. Second example
	{
		const list data{ 1, 2, 3, 4, 5, 6, 7 };
		assert(palindrome(data.begin(), data.end()) == false);
	}
}

void test_compress()
{
	typedef std::list<int> list;

	// a. An empty std::list
	{
		const list expected;
		const list   source;
		list         result;

		compress(source.begin(), source.end(), std::back_inserter(result));
		assert(result == expected);
	}

	// b. A non-empty std::list containing no consecutive duplicates
	{
		const list   source{ 1, 2, 3, 1, 2, 3 };
		list         result;

		compress(source.begin(), source.end(), std::back_inserter(result));
		assert(result == source);
	}

	// c. A non-empty std::list containing consecutive duplicates
	{
		const list expected{ 1, 2, 1 };
		const list   source{ 1, 1, 2, 2, 1, 1 };
		list         result;

		compress(source.begin(), source.end(), std::back_inserter(result));
		assert(result == expected);
	}
}

int main(void)
{
	test_palindrome();
	test_compress();
}