Algorithms

Here I want to outline the basic theory to developing algorithms

Statically typed inflexible algorithms

#include "stdafx.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <string.h>

#include "RememberMe.h"

using namespace std;
//---------------------------------------------------------------------------
void __fastcall algorithmsClick();

void	main()
{
	algorithmsClick();
}

namespace	s2s
{
	class _Equal
	{
	private:
		int value;
	public:
		_Equal(const int& v) : value(v) { }
		bool operator () (const int& v) const
		{
			return value == v;
		}
	};

	class _Neg
	{
	public:
		bool operator () (const int& v) const
		{
			return  v < 0;
		}
	};

	const int* begin(const vector<int> & v)
	{
		return v.empty() ? 0 : &v[0];
	}

	const int* end(const vector<int> & v)
	{
		return v.empty() ? 0 : (&v[v.size() - 1]) + 1;
	}

	const int* find(const int* first, const int* last, const int& value)
	{
		if (!*first || !last || (first == last))
			return last; // safeguard

		for (; first != last; ++first)
			if (*first == value) break;

		return first;
	}

	vector<int>::iterator& _find_if(vector<int>::iterator& first, 
									vector<int>::iterator& last, 
									_Equal& pred)
	{
		if (first == last)
			return last; // safeguard

		while (first != last && !pred(*first))
			++first;
		return first;
	}

	vector<int>::iterator& _find_if(vector<int>::iterator& first,
									vector<int>::iterator& last,
									_Neg& pred)
	{
		if (first == last)
			return last; // safeguard

		while (first != last && !pred(*first))
			++first;
		return first;
	}
};

void __fastcall algorithmsClick()
{
	vector<int> vi(10);

	for (unsigned i = 0; i < vi.size(); i++)
		vi[i] = 30 + i;

	const int *ibegin = s2s::begin(vi);
	const int *iend = s2s::end(vi);

	const int *val = s2s::find(ibegin, iend, 34);

	if (val)
		cout << "found " << *val << endl;

	val = s2s::find(ibegin, iend, 54);

	if (val == s2s::end(vi))
		cout << "End marker found looking for 54" << endl;

	// try out the equal functor
	vector<int>::iterator it;
	it = s2s::_find_if(vi.begin(), vi.end(), s2s::_Equal(5));
	if (it != vi.end())
		cout << "found " << *it << endl;

	// try out the Neg functor
	int ai_1[] = { 1, 2, 3, -5, 4, 5, 6 };
	vector<int> vi2(ai_1, ai_1 + sizeof(ai_1) / sizeof(int));
	it = s2s::_find_if(vi2.begin(), vi2.end(), s2s::_Neg());
	if (it != vi2.end())
		cout << "found value " << *it << endl;
	else
		cout << "no negative values" << endl;

	// try out the adapter
	int ai_2[] = { -1, -2, 3, -5, 4, 5, 6 };
	//int *itPtr = s2s::find_if(ai_2, ai_2 + 7, s2s::Not<s2s::Neg<int>>(s2s::Neg<int>()));
	//if (itPtr != vi.end())
	//	cout << "found value " << *itPtr;
}

Algorithms using Generics

#include "stdafx.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <string.h>

#include "RememberMe.h"

using namespace std;
//---------------------------------------------------------------------------
void __fastcall algorithmsClick();

void	main()
{
	algorithmsClick();
}

namespace	s2s
{
	template<typename T>
	const T* begin(const vector<T> & v)
	{
		return v.empty() ? 0 : &v[0];
	}

	template<typename T>
	const T* end(const vector<T> & v)
	{
		return v.empty() ? 0 : (&v[v.size()-1]) + 1;
	}

	template<typename T>
	const T* find(const T *first, const T* last, const T& value)
	{
		if (!first || !last || (first==last))   
			return last; // safeguard

		for (; first != last; ++first)
			if (*first == value) break;

		return first;
	}

	template <class InputIterator, class Predicate>
	InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
	{
		if (first == last)
			return last; // safeguard

		while (first != last && !pred(*first))
			++first;
		return first;
	}

	template <typename T>
	class Equal
	{
	private:
		T value;
	public:
		typedef   T   value_type;
		Equal(const T& v) : value(v) { }
		bool operator () (const T& v) const
		{
			return value == v;
		}
	};

	template<typename T>
	class Neg
	{
	public:
		typedef  T value_type;
		bool operator () (const T& v) const
		{
			return  v < 0;
		}
	};

/*
	template <typename Predicate>
	class Not
	{
		Predicate p;
	public:
		typedef Predicate::value_type value_type;
		Not(const Predicate& pred) : p(pred) {}
		bool operator () (const value_type& v) const
		{
			return !p(v);
		}
	};
	*/

	class any
	{
	public:
		// construct/copy/destruct
		any() {};
		any(const any &) {};
		template<typename ValueType> any(const ValueType &) {};
		any & operator=(const any & val) { return const_cast<any&>(val); };
		template<typename ValueType> any & operator=(const ValueType &val) { return val; };
		~any() {};
		// modifiers
		any & swap(any &val) { return val; };
		// queries
		bool empty() const { return true; };
		//++const std::type_info & type() const{ };
	};
};

void __fastcall algorithmsClick()
{
	vector<int> vi(10);

	for (unsigned i = 0; i < vi.size(); i++)
		vi[i] = 30 + i;

	const int *ibegin = s2s::begin(vi);
	const int *iend = s2s::end(vi);

	const int *val = s2s::find(ibegin, iend, 34);

	if (val)
		cout << "found " << *val << endl;

	val = s2s::find(ibegin, iend, 54);

	if (val == s2s::end(vi))
		cout << "End marker found looking for 54" << endl;

	// try out the equal functor
	vector<int>::iterator it;
	it = s2s::find_if(vi.begin(), vi.end(), s2s::Equal<int>(5));
	if (it != vi.end())
		cout << "found " << *it << endl;

	// try out the Neg functor
	int ai_1[] = { 1, 2, 3, -5, 4, 5, 6 };
	vector<int> vi2(ai_1, ai_1 + sizeof(ai_1) / sizeof(int));
	it = s2s::find_if(vi2.begin(), vi2.end(), s2s::Neg<int>());
	if (it != vi2.end())
		cout << "found value " << *it << endl;
	else
		cout << "no negative values" << endl;

	// try out the adapter
	int ai_2[] = { -1, -2, 3, -5, 4, 5, 6 };
	//int *itPtr = s2s::find_if(ai_2, ai_2 + 7, s2s::Not<s2s::Neg<int>>(s2s::Neg<int>()));
	//if (itPtr != vi.end())
	//	cout << "found value " << *itPtr;
}