//
// Copyright (c) 1999
// Kevin Atkinson
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without
// fee, provided that the above copyright notice appear in all copies
// and that both that copyright notice and this permission notice
// appear in supporting documentation.  I make no representations
// about the suitability of this software for any purpose.  It is
// provided "as is" without express or implied warranty.
//
// Enhancements and big fixes are encouraged.  Although you are not
// required to submit changes back it is strongly encouraged.  I can
// be reached at kevinatk@home.com.
//
#ifndef fiterators___
#define fiterators___

#include <iterator>
#include <typeinfo>

//
// virtual_forward_iterator is an abstract base clase for a forward iterator
//
template <class Ref> 
class virtual_forward_iterator {
public:
  typedef Ref reference;

  virtual reference dereference() const = 0;

  virtual void increment() = 0;
                            // like operator++ but doesn't return anything

  virtual virtual_forward_iterator * clone() const = 0; 
                            // return a copy of itself allocated with new

  virtual ~virtual_forward_iterator() {}

  virtual bool is_equal (const virtual_forward_iterator&) const = 0;
};

//
// A valid forward iterator that inherates from add_virtual_forward_iterator
// will also become a virtual_forward_iterator
//
template <class Itr, class VirRef = iterator_traits<Itr>::reference>
class add_virtual_forward_iterator : public virtual_forward_iterator<VirRef> {
private:
  typedef virtual_forward_iterator<VirRef> Base;
  typedef Itr                              Derived;
public:
  typedef VirRef virtual_reference;
  bool is_equal (const Base &other) const; 
    // Note: other must be an Itr or else is_equal is undefined
  void increment();
  Base * clone() const;
  virtual_reference dereference() const;
};

//
// Makes a normal forward iterator a virtual forward iterator
//

template <class Iterator, 
          class VirReference = iterator_traits<Iterator>::reference>
class make_virtual_forward_iterator 
  : public add_virtual_forward_iterator
   <
      make_virtual_forward_iterator<Iterator,VirReference>,
      VirReference
   >
{
public:
  typedef forward_iterator_tag                       iterator_category;
  typedef iterator_traits<Iterator>::value_type      value_type;
  typedef iterator_traits<Iterator>::difference_type difference_type;
  typedef iterator_traits<Iterator>::reference       reference;
  typedef iterator_traits<Iterator>::pointer         pointer; 
  typedef Iterator                                   real_iterator;
protected:
  typedef make_virtual_forward_iterator        Self;
private:
  Iterator itr;
public:
  make_virtual_forward_iterator() {}
  make_virtual_forward_iterator(Iterator i) : itr(i) {}
  reference operator*() const {return *itr;}
  Self& operator++() {++itr; return *this;}
  Self operator++(int) {Self temp = *this; ++itr; return temp;}
  bool is_equal(Self other) const {return itr == other.itr;}
};

#define TL template <class Iterator, class VirReference>
#define SELF make_virtual_forward_iterator<Iterator, VirReference>

TL inline bool operator==(SELF rhs, SELF lhs) {return rhs.is_equal(lhs);}
TL inline bool operator!=(SELF rhs, SELF lhs) {return !rhs.is_equal(lhs);}

#undef TL
#undef SELF

template <class VirRef, class Itr>
make_virtual_forward_iterator<Itr, VirRef> make_virtual_forward_iteratorr(Itr i) {
  return make_virtual_forward_iterator<Itr, VirRef>(i);
}
//
// virtual_forward_iterator_proxy hides the fact that you are really 
// dealing with a virtual object.  It behaves just like any other
// forward iterator with a few extra member functions.
// 

template <class Value, class Ref = const Value &, 
          class Pointer = const Value *, class Difference = long>
class virtual_forward_iterator_proxy {
public:
  typedef forward_iterator_tag iterator_category;
  typedef Value                value_type;
  typedef Difference           difference_type;
  typedef Ref                  reference;
  typedef Pointer              pointer;
private:
  typedef virtual_forward_iterator<Ref>    RealItr;
  typedef virtual_forward_iterator_proxy   Self;

  RealItr *itr;
public:
  virtual_forward_iterator_proxy() {itr = 0;}
  virtual_forward_iterator_proxy(const RealItr& i)  {itr = i.clone();}
  virtual_forward_iterator_proxy(const Self& other) 
    {if (other.itr) itr = other.itr->clone(); else itr = 0;}
  Self& operator= (const Self& other) {
    if (this != &other) {
      delete itr;
      if (other.itr) 
	itr = other.itr->clone(); 
      else 
	itr = 0;
    }
    return *this;
  }
  ~virtual_forward_iterator_proxy() {delete itr;}

  Ref operator*() const {return itr->dereference();}

  Self& operator++() {itr->increment(); return *this;}
  Self operator++(int) {Self temp=*this; itr->increment(); return temp;}

  const type_info & id() const {return typeid(*itr);}
  
  bool is_equal(const Self &other) const {return itr->is_equal(*other.itr);}
};

#define TL template <class Value, class Ref, class Pointer, class Difference> 
#define SELF virtual_forward_iterator_proxy<Value, Ref, Pointer, Difference>

TL inline bool operator==(const SELF & lhs, const SELF & rhs) {
  return lhs.is_equal(rhs);
}

TL inline bool operator!=(const SELF & lhs, const SELF & rhs) {
  return !lhs.is_equal(rhs);
}

#undef TL
#undef SELF

//
// MultiForwardIterator will iterate through the range of a series
// of iterators as if there where one iterator.
//
// MultiItr must be a Forward iterator that has a value type that is a
// class that has the members begin() & end() that return a RealItr
// RealItr must also be a forward_iterator.
// 
//
template < class MultiItr, 
           class RealItr = typename iterator_traits<MultiItr>::value_type::const_iterator
         >
class multi_forward_iterator 
{
public:
  typedef MultiItr outer_iterator;
  typedef RealItr  inner_iterator;
  typedef forward_iterator_tag                      iterator_category;
  typedef iterator_traits<RealItr>::value_type      value_type;
  typedef iterator_traits<RealItr>::difference_type difference_type;
  typedef iterator_traits<RealItr>::pointer         pointer;
  typedef iterator_traits<RealItr>::reference       reference;

private:
  typedef multi_forward_iterator        Self;

  MultiItr   cur;
  MultiItr   end;
  RealItr    itr;
public:
  multi_forward_iterator() {}

  multi_forward_iterator(MultiItr c, MultiItr e, RealItr i)
    : cur(c), end(e), itr(i)   {}
  multi_forward_iterator(MultiItr c, MultiItr e)
    : cur(c), end(e)           {}
  reference operator*() const {return *itr;}
  Self& operator++();
  Self operator++(int) {Self temp=*this; operator++(); return temp;}

  bool is_equal(const Self &other) const {
    return cur == other.cur && (cur == end || itr == other.itr);
  }
};

#define TL template <class MultiItr, class RealItr>
#define SELF multi_forward_iterator<MultiItr, RealItr>

TL inline bool operator==(const SELF& lhs, const SELF& rhs) {
  return lhs.is_equal(rhs);
}

TL inline bool operator!=(const SELF& lhs, const SELF& rhs) {
  return !lhs.is_equal(rhs);
}

#undef TL
#undef SELF

//
// ConstMultiForwardContainer is a forward container which simply holds
// another container of container like objects and iterates through them
// as if they where one.
//
// ItrCon is a forward container whoes value type is a structure which
// has at least the following public members begin(), end(), and
// size().  begin() and end() must return forward iterators.

template <class ItrCon>
class const_multi_forward_container {
private:
public:
  typedef ItrCon                                     outer_container;
  typedef typename outer_container::const_iterator   outer_iterator;
  typedef 
    typename iterator_traits<outer_iterator>::value_type::const_iterator 
                                                      inner_iterator;
  typedef iterator_traits<inner_iterator>::value_type value_type;
  typedef typename ItrCon::value_type::size_type      size_type;
  typedef multi_forward_iterator<outer_iterator>      const_iterator;
  typedef const_iterator                              iterator;

  static const size_type npos = -1;

private:
  ItrCon            itrs;
  mutable size_type size_;
public:
  const_multi_forward_container() : size_(0) {}
  const_multi_forward_container(const ItrCon& c) : size_(npos) {itrs=c;}
  const_multi_forward_container& swap_in(ItrCon &c) 
    {swap(itrs,c); size_ = npos; return *this;}
  const_multi_forward_container& copy_in(const ItrCon &c) 
    {itrs = c; size_ = npos; return *this;}
  const_iterator begin() const;
  const_iterator end() const {return const_iterator(itrs.end(), itrs.end());}
  size_type size() const;
  bool empty() const {return itrs.empty();}
};

template <class Itr, class Size = size_t>
struct begin_end_size {
  typedef Itr  iterator;
  typedef Itr  const_iterator;
  typedef Size size_type;
  Itr  begin_;
  Itr  end_;
  Size size_;
  Itr begin() const {return begin_;}
  Itr end() const {return end_;}
  Size size() const {return size_;}
  bool empty() const {return !size_;}
  begin_end_size() : size_(0) {}
  begin_end_size(Itr b, Itr e, Size s) : begin_(b), end_(e), size_(s) {}
};

template <class Itr, class DeRefFunc, class Value, class Ref, class Pointer>
class alt_dereference_iterator {
public:
  typedef iterator_traits<Itr>::iterator_category iterator_category;
  typedef iterator_traits<Itr>::difference_type   difference_type;
  typedef Value                                   value_type;
  typedef Ref                                     reference;
  typedef Pointer                                 pointer;
private:
  Itr       itr_;
  DeRefFunc deref_;
public:
  alt_dereference_iterator() {}
  alt_dereference_iterator(Itr i, const DeRefFunc &drf = DeRefFunc())
    : itr_(i), deref_(drf) {}
  reference operator*() const {return deref_(itr_);}
  pointer   operator->() const {return &deref_(itr_);}
  alt_dereference_iterator& operator++() {++itr_; return *this;}
  alt_dereference_iterator& operator++(int) 
    {alt_dereference_iterator temp=*this; ++itr_; return temp;}
  bool is_equal(alt_dereference_iterator other) const 
    {return itr_ == other.itr_;}
};

#define TL template <class Itr, class DeRefFunc, class Value, class Ref, class Pointer>
#define SELF alt_dereference_iterator<Itr,DeRefFunc,Value,Ref,Pointer>

TL inline bool operator==(SELF rhs, SELF lhs) {return rhs.is_equal(lhs);}
TL inline bool operator!=(SELF rhs, SELF lhs) {return !rhs.is_equal(lhs);}

#undef TL
#undef SELF

template <class Itr, class DeRefFunc, class Value, class Ref, class Pointer>
class alt_deref_make_virtual_forward_iterator 
  : public make_virtual_forward_iterator <
      alt_dereference_iterator<Itr,DeRefFunc,Value,Ref,Pointer>
    >
{
protected:
  typedef Self Parent;
public:
  alt_deref_make_virtual_forward_iterator() {}
  alt_deref_make_virtual_forward_iterator(real_iterator i) : Parent(i) {}
  alt_deref_make_virtual_forward_iterator(Itr i, const DeRefFunc &drf = DeRefFunc())
    : Parent(alt_dereference_iterator<Itr,DeRefFunc,Value,Ref,Pointer>(i, drf)) {}
};

#define ITR  typename Con::const_iterator
#define RITR typename RealCon::const_iterator
#define ITRT iterator_traits<ITR>

template <class Con, class RealCon> 
begin_end_size<virtual_forward_iterator_proxy<ITRT::value_type, ITRT::reference> > 
make_virtual_const_begin_end_sizer(const RealCon& con) 
{
  return begin_end_size
    <virtual_forward_iterator_proxy<ITRT::value_type,ITRT::reference > > 
    (
     make_virtual_forward_iterator<RITR,ITRT::reference>(con.begin()),
     make_virtual_forward_iterator<RITR,ITRT::reference>(con.end()),
     con.size()
    );
}

#undef ITR
#undef ITRT

template <class MultiItr, class RealItr>
multi_forward_iterator<MultiItr, RealItr>&
multi_forward_iterator<MultiItr, RealItr>::operator++() {
  ++itr;
  if (itr == (*cur).end()) {
    ++cur;
    if (!(cur == end))
      itr = (*cur).begin();
  }
  return *this;
}

#define TL template <class Itr, class VRef>
#define SELF add_virtual_forward_iterator<Itr, VRef>

TL bool SELF::is_equal (const SELF::Base &other) const {
  return *static_cast<const Itr *>(this) == *static_cast<const Itr *>(&other);
}

TL void SELF::increment() {
    static_cast<Itr *>(this)->operator++();
}

TL SELF::Base * SELF::clone() const {
  return new Itr(*static_cast<const Itr *>(this));
}
 
TL SELF::virtual_reference SELF::dereference() const {
  return static_cast<const Itr *>(this)->operator*();
}

#undef TL
#undef SELF

template <class ItrCon>
const_multi_forward_container<ItrCon>::const_iterator 
const_multi_forward_container<ItrCon>::begin() const {
  if (itrs.begin() != itrs.end())
    return const_iterator(itrs.begin(), itrs.end(), itrs.begin()->begin());
  else
    return end();
}

template <class ItrCon>
const_multi_forward_container<ItrCon>::size_type
const_multi_forward_container<ItrCon>::size() const {
  if (size_ == npos) {
    size_ = 0;
    outer_iterator i = itrs.begin();
    outer_iterator e = itrs.end();
    for (; i != e; ++i)
      size_ += i->size();
  }
  return size_;
}

template <typename InputIterator, typename Func> 
bool try_each(InputIterator i, InputIterator end, Func f) {
  while(i != end) {
    if (f(i)) return true;
    ++i;
  }
  return false;
}

#endif
