// oo_template_iterator.C
// ----------------------------------------------------------------
// COMP 290-001: Algorithm Library Design, Lutz Kettner, 01/11/2000
// Solution for Exercise 3b, an iterator design following OO principles
// combined with templates.


// A common base class for all iterators. Generic value type T.
template <class T>
struct Iterator {
    virtual void advance()               = 0;
    virtual bool equal( Iterator<T>* i)  = 0;
    virtual T    get()                   = 0;
    virtual ~Iterator() {}
};

template <class T>
class Array_iterator : public Iterator<T> {
    T* s;
public:
    Array_iterator() : s(0) {}
    Array_iterator( T* p) : s(p) {}
    virtual void advance() {
	++s;
    }
    virtual bool equal( Iterator<T>* i) {
	if ( dynamic_cast< Array_iterator<T>*>(i))
	    return s == dynamic_cast< Array_iterator<T>*>(i)->s;
	return false;
    }
    virtual T    get() {
	return *s;
    }
};


// Write a generic function that finds a value in a range of two iterators.
template <class T>
bool contains( Iterator<T>* first, Iterator<T>* last, const T& c) {
    while ( ! first->equal( last)) {
	if ( first->get() == c)
	    return true;
	first->advance();
    }
    return false;
}


// A small test program.
#include <assert.h>

int main() {
    {
	char* s = "Some useless text.";
	Array_iterator<char>* begin = new  Array_iterator<char>(s);
	Array_iterator<char>* last  = new  Array_iterator<char>(s+18);
	assert(   contains( begin, last, 'u'));
        delete begin;
	begin = new  Array_iterator<char>(s);
	assert( ! contains( begin, last, 'q'));
	delete begin;
	delete last;
    }{
	int p[5];
	p[0] = 2;
	p[1] = 3;
	p[2] = 5;
	p[3] = 7;
	p[4] = 11;
	Array_iterator<int>* begin = new  Array_iterator<int>(p);
	Array_iterator<int>* last  = new  Array_iterator<int>(p+5);
	assert(   contains( begin, last, 5));
        delete begin;
	begin = new  Array_iterator<int>(p);
	assert( ! contains( begin, last, 9));
	delete begin;
	delete last;
    }
}