Re: (infinite) sequences using recurrence relations

From: Eric Ford (eford_at_[hidden])
Date: 2001-08-08 15:26:47

Based on the comments here, I've updated my attempt at implementing
recurrent itterators and sequences.  The goal is to make it easy to
implement stl compliant itterators based on user provided recurrence
relations.  People particularly interested, can check the new files (I
even tried to improve the README).  

Out of respect to Jeremy, here's a snippet of code showing how I'll
post an extract that should provide ample evidence for discussing how
it doesn't quite meet all the requirements for a real iterator.

// from recurrent_iterator.h

template<class RecurrenceType>
class recurrence_trivial_iterator
{
  typedef RecurrenceType recurrence_type;
  typedef recurrence_trivial_iterator<recurrence_type>
trivial_iterator ;
  typedef trivial_iterator iterator;
  typedef typename recurrence_type::value_type value_type;
  typedef value_type* pointer;
  typedef value_type& reference;
  typedef int difference_type;   

 protected:  // internals
  recurrence_type mRecurrence;
  recurrence_type&       get_recurrence() { return mRecurrence; };
  const recurrence_type& get_recurrence() const { return mRecurrence;
};
  
 public:
  explicit recurrence_trivial_iterator(recurrence_type Recurrence) :
mRecurrence(Recurrence) {};

  // iterator operations
  value_type operator*() { return get_recurrence().get_value(); };

  // comparison operators get passed along to recurrence relation 
  bool operator==(iterator b) const { return
(get_recurrence()==b.get_recurrence()); };
  bool operator!=(iterator b) const { return !operator==(b); };
  bool operator<(iterator b) const { return
(get_recurrence()<b.get_recurrence()); };
  bool operator>(iterator b) const { return
(b.get_recurrence()<get_recurrence()); };
  bool operator<=(iterator b) const { return !operator>(b); };
  bool operator>=(iterator b) const { return !operator<(b); };

  // valid iterator checks
  bool is_valid() const { return get_recurrence().is_valid(); };

};  

template<class RecurrenceType>
class recurrence_bidirectional_iterator : public
recurrence_trivial_iterator<RecurrenceType>
{
  typedef recurrence_bidirectional_iterator<recurrence_type>
bidirectional_iterator;
  typedef bidirectional_iterator iterator;

 public:
  explicit recurrence_bidirectional_iterator(recurrence_type
Recurrence)  : trivial_iterator(Recurrence) {};

  // iterator operations
  iterator operator++() { get_recurrence().next();  return *this; };
  iterator operator--() { get_recurrence().prev();  return *this; };

  // valid iterator checks
  bool is_next_valid() const { return
get_recurrence().is_next_valid(); };
  bool is_prev_valid() const { return
get_recurrence().is_prev_valid(); };
};  

// from fibbonaci.h
template<class Type>
class fibbonaci_recurrence 
{
  // provide value_type (type returned by get_value) and appropriate
iterator
  typedef Type value_type;
  typedef fibbonaci_recurrence<value_type> self_type;
  typedef recurrence_bidirectional_iterator<self_type> iterator;

 protected:
  // internals
  typedef std::pair<value_type, value_type> state_type;
  state_type mState;
  void set_state(state_type State) { mState = State; };
  const state_type get_state() const { return mState; };

  static const value_type mMinValue = 0;
  static const value_type mMaxValue = 10000;
  
 public:
  // provide constructor
  explicit fibbonaci_recurrence(state_type State) : mState(State) {};

  // provide current value
  value_type get_value() const { return get_state().first; };

  // provide means of calculating new state, since bidirectional need
to provide next and prev
  self_type next() {
set_state(state_type(mState.first+mState.second,mState.first)); 
return *this;  };
  self_type prev() {
set_state(state_type(mState.second,mState.first-mState.second));
return *this;  };

  // provide comparison operators
  bool operator==(self_type b) const { return
(get_state()==b.get_state()); };
  bool operator<(self_type b) const { return (get_value() <
b.get_value()); };

  // provide validity checks
  bool is_valid() const { return true; };
  bool is_next_valid() const { return (get_state().first <=
mMaxValue-get_state().second ); };
  bool is_prev_valid() const { return (get_state().first >=
mMinValue+get_state().second ); };
};

That should allow operations like

fibbonaci_recurrence<int> fr(make_pair(1,0));  // initializing a
recurrence relation
recurrence_bidirectional_iterator< fibbonaci_recurrence<int> >
f(fr);    // initialization a recurrent iterator

cout << *f << endl; ++f;  cout << *f << endl; ++f;  cout << *f <<
endl; ++f;  cout << *f << endl; --f;  cout << *f << endl;

The question is there something it should allow that it doesn't...