/**************************************************
 * Essential C++ -- Stanley Lippman
 * Addison-Wesley 
 * ISBN 0-201-48518-4
 * homepage: www.objectwrite.com
 * email: slippman@objectwrite.com
 *************************************************/

#include <map>
#include <string>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;

// various test programs
extern void prog1();
extern void prog2();
extern void prog3();

int main()
{
	// prog1();
	// prog2();
	prog3();

	return 0; // quiets vc++
}

class num_sequence;
ostream& operator<<( ostream &os, const num_sequence &ns );

class num_sequence {
public:
	typedef vector<unsigned int>::iterator iterator;

    virtual ~num_sequence(){};
	virtual num_sequence *clone() const = 0;
			 
	virtual unsigned int elem( int pos ) const = 0;
	virtual bool         is_elem(  unsigned int ) const=0;
	virtual int          pos_elem( unsigned int ) const=0;

    virtual const char*  what_am_i() const = 0;
	static  int          max_elems(){ return _max_elems; }
	virtual ostream&     print( ostream &os = cout ) const = 0;
	
	virtual bool operator ==( const num_sequence& ) const=0;
    virtual bool operator !=( const num_sequence& ) const=0;
	
	// to work, need to remove all pure virtual functions
    // virtual num_sequence operator+( const num_sequence& ) const=0;

	virtual iterator begin() const = 0;
	virtual iterator end() const = 0;

	virtual int length()  const = 0;
    virtual int beg_pos() const = 0; 

	virtual void set_position( int pos ) = 0;
	virtual void set_length( int pos ) = 0;

	virtual	const vector<unsigned int>* sequence() const=0;
  
protected:
	// static const int    _max_elems = 1024;	
	// for compilers not supporting const static
	enum { _max_elems = 1024 };

    virtual void gen_elems( int pos ) const = 0;
	bool check_integrity( int pos, int size ) const; 
};

ostream& operator<<( ostream &os, const num_sequence &ns )
{  
    return ns.print( os );
}

class Fibonacci : public num_sequence {
public:
   Fibonacci( int beg_pos = 1, int len = 1 )
   {  set_position( beg_pos ); set_length( len ); }

   virtual num_sequence *clone() const 
		 { return new Fibonacci( *this ); }
		
   virtual unsigned int elem( int pos ) const;
   virtual bool        is_elem(  unsigned int elem ) const;
   virtual int         pos_elem( unsigned int elem ) const;

   virtual const char* what_am_i() const { return "Fibonacci"; }
   virtual ostream&    print( ostream &os = cout ) const; 

   virtual bool operator==( const num_sequence &rhs ) const;
   virtual bool operator!=( const num_sequence &rhs ) const; 

   virtual int length()  const { return _length;  }
   virtual int beg_pos() const { return _beg_pos; }

   virtual void set_position( int pos );
   virtual void set_length( int pos );

   virtual iterator begin() const 
		 { return _elems.begin()+_beg_pos-1; }

   virtual iterator end() const 
		 { return _elems.begin() + _beg_pos + _length; }	 

   virtual const vector<unsigned int>* 
	     sequence() const { return & _elems; }

protected:
   virtual void gen_elems( int pos ) const;
   static vector< unsigned int > _elems;
   
   int _length; 	
   int _beg_pos; 

private:
	int _calc_pos( unsigned int elem ) const;
};

class Pell : public num_sequence {
public:
   Pell( int beg_pos = 1, int len = 1 )
   {  set_position( beg_pos ); set_length( len ); }

   virtual num_sequence *clone() const 
		 { return new Pell( *this ); }
		
   virtual unsigned int elem( int pos ) const;
   virtual bool is_elem(  unsigned int elem ) const;
   virtual int pos_elem( unsigned int elem ) const;

   virtual const char* what_am_i() const { return "Pell"; }
   virtual ostream&    print( ostream &os = cout ) const; 

   virtual int length()  const { return _length;  }
   virtual int beg_pos() const { return _beg_pos; }

   virtual void set_position( int pos );
   virtual void set_length( int pos );

   virtual bool operator==( const num_sequence &rhs ) const;
   virtual bool operator!=( const num_sequence &rhs ) const; 

   virtual iterator begin() const 
		 { return _elems.begin()+_beg_pos-1; }

   virtual iterator end() const 
		 { return _elems.begin() + _beg_pos + _length; }

   virtual const vector<unsigned int>* 
	     sequence() const { return & _elems; }

protected:
   virtual void gen_elems( int pos ) const;
   static vector< unsigned int > _elems;
   
   int _length; 	
   int _beg_pos; 

private:
	int _calc_pos( unsigned int elem ) const;
};

class Lucas : public num_sequence {
public:
   Lucas( int beg_pos = 1, int len = 1 )
   {  set_position( beg_pos ); set_length( len ); }

   virtual num_sequence *clone() const 
		 { return new Lucas( *this ); }
		
   virtual unsigned int elem( int pos ) const;
   virtual bool        is_elem(  unsigned int elem ) const;
   virtual int         pos_elem( unsigned int elem ) const;

   virtual const char* what_am_i() const { return "Lucas"; }
   virtual ostream&    print( ostream &os = cout ) const; 

   virtual int length()  const { return _length;  }
   virtual int beg_pos() const { return _beg_pos; }

   virtual void set_position( int pos );
   virtual void set_length( int pos );

   virtual bool operator==( const num_sequence &rhs ) const;
   virtual bool operator!=( const num_sequence &rhs ) const; 

   virtual iterator begin() const 
		 { return _elems.begin()+_beg_pos-1; }

   virtual iterator end() const 
		 { return _elems.begin() + _beg_pos + _length; }

   virtual const vector<unsigned int>* 
	     sequence() const { return & _elems; }

protected:
   virtual void gen_elems( int pos ) const;
   static vector< unsigned int > _elems;
   	 
   int _length; 	
   int _beg_pos; 

private:
	int _calc_pos( unsigned int elem ) const;
};

class Triangular : public num_sequence {
public:
   Triangular( int beg_pos = 1, int len = 1 )
   {  set_position( beg_pos ); set_length( len ); }

   virtual num_sequence *clone() const 
		 { return new Triangular( *this ); }
		
   virtual unsigned int elem( int pos ) const;
   virtual bool is_elem(  unsigned int elem ) const;
   virtual int  pos_elem( unsigned int elem ) const;

   virtual const char* what_am_i() const { return "Triangular"; }
   virtual ostream&    print( ostream &os = cout ) const; 

   virtual int length()  const { return _length;  }
   virtual int beg_pos() const { return _beg_pos; }

   virtual void set_position( int pos );
   virtual void set_length( int pos );

   virtual bool operator==( const num_sequence &rhs ) const;
   virtual bool operator!=( const num_sequence &rhs ) const; 

   virtual iterator begin() const 
		 { return _elems.begin()+_beg_pos-1; }

   virtual iterator end() const 
		 { return _elems.begin() + _beg_pos + _length; }

   virtual const vector<unsigned int>* 
	     sequence() const { return & _elems; }

protected:
   virtual void gen_elems( int pos ) const;
   static vector< unsigned int > _elems;
   	
   int _length; 	
   int _beg_pos;
   
private:
	int _calc_pos( unsigned int elem ) const;
};

class Square : public num_sequence {
public:
   Square( int beg_pos = 1, int len = 1 )
   {  set_position( beg_pos ); set_length( len ); }

   virtual num_sequence *clone() const 
		 { return new Square( *this ); }
		
   virtual unsigned int elem( int pos ) const;
   virtual bool        is_elem(  unsigned int elem ) const;
   virtual int         pos_elem( unsigned int elem ) const;

   virtual const char* what_am_i() const { return "Square"; }
   virtual ostream&    print( ostream &os = cout ) const; 

   virtual int length()  const { return _length;  }
   virtual int beg_pos() const { return _beg_pos; }

   virtual void set_position( int pos );
   virtual void set_length( int pos );

   virtual bool operator==( const num_sequence &rhs ) const;
   virtual bool operator!=( const num_sequence &rhs ) const; 

   virtual iterator begin() const 
		 { return _elems.begin()+_beg_pos-1; }

   virtual iterator end() const 
		 { return _elems.begin() + _beg_pos + _length; }

   virtual const vector<unsigned int>* 
	     sequence() const { return & _elems; }

protected:
   virtual void gen_elems( int pos ) const;
   static vector< unsigned int > _elems;
   	
   int _length; 	
   int _beg_pos; 

private:
	int _calc_pos( unsigned int elem ) const;
};

class Pentagonal : public num_sequence {
public:
   Pentagonal( int beg_pos = 1, int len = 1 )
   {  set_position( beg_pos ); set_length( len ); }

   virtual num_sequence *clone() const 
		 { return new Pentagonal( *this ); }
		
   virtual unsigned int elem( int pos ) const;
   virtual bool        is_elem(  unsigned int elem ) const;
   virtual int         pos_elem( unsigned int elem ) const;

   virtual const char* what_am_i() const { return "Pentagonal"; }
   virtual ostream&    print( ostream &os = cout ) const; 

   virtual int length()  const { return _length;  }
   virtual int beg_pos() const { return _beg_pos; }

   virtual void set_position( int pos );
   virtual void set_length( int pos );

   virtual bool operator==( const num_sequence &rhs ) const;
   virtual bool operator!=( const num_sequence &rhs ) const; 

   virtual iterator begin() const 
		 { return _elems.begin()+_beg_pos-1; }

   virtual iterator end() const 
		 { return _elems.begin() + _beg_pos + _length; }

   virtual const vector<unsigned int>* 
	     sequence() const { return & _elems; }

protected:
   virtual void gen_elems( int pos ) const;
   static vector< unsigned int > _elems;
   	
   int _length; 	
   int _beg_pos; 

private:
	int _calc_pos( unsigned int elem ) const;
};

inline void 
display( ostream &os, const num_sequence &ns, 
		 int pos, int elem_val )
{
	os << "The element at position " << pos 
	   << " for the "
	   << ns.what_am_i() 
	   << " sequence is " << elem_val << endl;
}

inline void 
display( ostream &os, const num_sequence &ns, int pos )
{
	os << "The element at position " 
	   << pos            << " for the "
	   << ns.what_am_i() << " sequence is " 
	   << ns.elem( pos ) << endl;
}

// actual programs exercising the hierarchy
// normally would go in a program text file: .cpp

void prog1()
{
	const int pos = 8;

	Fibonacci fib;	
	display( cout, fib, pos );

	Pell pell;
	display( cout, pell, pos );

	Lucas lucas;
	display( cout, lucas, pos );

	Triangular trian;
	display( cout, trian, pos );
	
	Square square;
	display( cout, square, pos );

	Pentagonal penta;
    display( cout, penta, pos );

}

void prog2()
{
	Fibonacci  fib( 1, 8 );
	Pell       pell( 4, 6 );
	Lucas      lucas( 7, 10 );
	Triangular trian( 1, 12 );
	Square     square( 6, 6 );
	Pentagonal penta( 1, 8 );

	cout << "fib: " << fib << '\n'
	     << "pell: " << pell << '\n'
		 << "lucas: " << lucas << '\n'
		 << "trian: " << trian << '\n'
		 << "square: " << square << '\n'
		 << "penta: " << penta << endl;
};

void prog3()
{
	num_sequence *pns = 0;
	int elem_val = 0;
	const int pos = 8;
	const int find_pos = 14;

	int elem_values[] = { 377, 80782, 843, 105, 196, 287 }; 
	// for ( int ix = 0; ix < 6; ++ix ) // test all
	for ( int ix = 0; ix < 1; ++ix ) // test 1 at time
	{
		// for testing, just insure that we try
		// out each derived class instance ...

		switch( ix ) {
		case 0:
			pns = new Fibonacci( 1, 8 );
			break;
		case 1:
			delete pns;
			pns = new Pell( 1, 8 );
			break;
		case 2:
			delete pns;
			pns = new Lucas( 1, 8 );
			break;
		case 3:
			delete pns;
			pns = new Triangular( 1, 8 );
			break;
		case 4:
			delete pns;
			pns = new Square( 1, 8 );
			break;