/
Algorithms
Algorithms
- Selvyn Wright
Owned by Selvyn Wright
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;
}