#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <boost/utility.hpp>
#include <boost/smart_ptr.hpp>

//#define OLD_ITERATORS
#ifdef OLD_ITERATORS
#include <boost/iterator_adaptors.hpp>
#else
#include <boost/iterator/indirect_iterator.hpp>
#include <boost/iterator/reverse_iterator.hpp>
#endif


namespace ZUtil
{
#ifdef OLD_ITERATORS
   struct shared_ptr_iterator_policies : public boost::default_iterator_policies
   {
      //T is the class that SmartList<T> gets created with.
      //Iterator is a vector<shared_ptr<T> >::iterator
      //template<class T, class Iterator>
      //T dereference(boost::type<T>, const Iterator& i) const { return *(*i); }
      template <class IteratorAdaptor>
         typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
      { return *(*x.base()); }
      template<class T1, class T2>
         bool less(T1& x, T2& y) const { return &(*x) < &(*y); }
   };

   //T is what SmartList is holding
   template<class T, class Iterator, class ConstIterator>
   struct shared_ptr_iterator_generator
   {
      typedef boost::iterator_adaptor<Iterator, shared_ptr_iterator_policies, T, T&, T*> ItrAdapter;
      typedef boost::iterator_adaptor<ConstIterator, shared_ptr_iterator_policies, T, const T&, const T*> ConstItrAdapter;
   };
#endif

   template<class T>
   class SmartList
   {
   private:
      typedef typename std::vector<boost::shared_ptr<T> >::iterator native_iterator;
      typedef typename std::vector<boost::shared_ptr<T> >::const_iterator const_native_iterator;

   public:
      SmartList() {}
      virtual ~SmartList() {}

#ifdef OLD_ITERATORS
   public:
      typedef typename shared_ptr_iterator_generator<T, native_iterator, const_native_iterator>::ItrAdapter iterator;
      typedef typename shared_ptr_iterator_generator<T, native_iterator, const_native_iterator>::ConstItrAdapter const_iterator;
      typedef typename boost::reverse_iterator_generator<iterator>::type rev_iterator;
      typedef typename boost::reverse_iterator_generator<const_iterator>::type const_rev_iterator;

      SmartList() {}
      virtual ~SmartList() {}

      inline iterator begin() { return iterator(items.begin()); }
      inline iterator end() { return iterator(items.end()); }
      inline const_iterator begin() const { return const_iterator(items.begin()); }
      inline const_iterator end() const { return const_iterator(items.end()); }

      inline rev_iterator rbegin() { return rev_iterator(end()); }
      inline rev_iterator rend() { return rev_iterator(begin()); }
      inline const_rev_iterator rbegin() const { return const_rev_iterator(end()); }
      inline const_rev_iterator rend() const { return const_rev_iterator(begin()); }


#else // NEW_ITERATORS
   private:
      typedef typename std::vector<boost::shared_ptr<T> >::reverse_iterator rev_native_iterator;
      typedef typename std::vector<boost::shared_ptr<T> >::const_reverse_iterator rev_const_native_iterator;

   public:
      //typedef boost::indirect_iterator<native_iterator> iterator;
      //typedef boost::indirect_iterator<const_native_iterator, T const> const_iterator;
      //typedef boost::reverse_iterator<iterator> rev_iterator;
      //typedef boost::reverse_iterator<const_iterator> const_rev_iterator;
      typedef boost::indirect_iterator<native_iterator>  iterator;
      typedef boost::indirect_iterator<const_native_iterator, T const> const_iterator;
      typedef typename boost::reverse_iterator<iterator> rev_iterator;
      typedef typename boost::reverse_iterator<const_iterator> const_rev_iterator;

      inline iterator begin() { return iterator(items.begin()); }
      inline iterator end() { return iterator(items.end()); }
      inline const_iterator begin() const { return const_iterator(items.begin()); }
      inline const_iterator end() const { return const_iterator(items.end()); }

      //inline rev_iterator rbegin() { return rev_iterator(rbegin()); }
      //inline rev_iterator rend() { return rev_iterator(rend()); }
      //inline const_rev_iterator rbegin() const { return const_rev_iterator(rbegin()); }
      //inline const_rev_iterator rend() const { return const_rev_iterator(rend()); }
      inline rev_iterator rbegin() { return rev_iterator(end()); }
      inline rev_iterator rend() { return rev_iterator(begin()); }
      inline const_rev_iterator rbegin() const { return const_rev_iterator(end()); }
      inline const_rev_iterator rend() const { return const_rev_iterator(begin()); }

#endif
      inline T& front() { return *(items.front()); }
      inline T const& front() const { return *(items.front()); }
      inline T& back() { return *(items.back()); }
      inline T const& back() const { return *(items.back()); }

      inline int size() const { return (int)items.size(); }
      inline void sort() { std::sort(begin(), end()); }
      inline void rsort() { std::sort(rbegin(), rend()); }
      inline void clear() { items.clear(); }

      inline iterator erase(iterator it) 
      { return iterator(items.erase(items.begin()+(it - begin()))); }

      inline iterator erase(iterator first, iterator last) 
      { return iterator(items.erase(first.base(), last.base()) ); }

      void append(T* t);
      void append(SmartList const& rl);
      void append(iterator it);

      inline T& operator[](size_t n) { return *(items[n]); }
      inline T const& operator[](size_t n) const { return *(items[n]); }

      size_t capacity() const { return items.capacity(); }
      void reserve(size_t n) { items.reserve(n); }

      void swap(SmartList& list) { items.swap(list.items); }

      bool empty() { return items.empty(); } 

   private:
      std::vector<boost::shared_ptr<T> > items;
   };

template<class T>
void 
SmartList<T>::append(SmartList<T> const& rl)
{
   if(this == &rl) {
      throw std::runtime_error("SmartList<T>::append, cannot append a SmartList to itslf.");
   }
   items.insert(items.end(), rl.items.begin(), rl.items.end());
}

template<class T>
void 
SmartList<T>::append(T* t)
{
   if(!t) {
      throw std::runtime_error("SmartList<T>::append, cannot append a 0x00 pointer.");
   }

   items.push_back(boost::shared_ptr<T>(t));
}

template<class T>
void 
SmartList<T>::append(iterator it)
{
   items.push_back(*(it.base()));
}

} //namespace ZUtil

class TestItem
{
public:
   TestItem() {
      memcpy(freak, "I am a freak", sizeof(freak));
      freak[12] = '\0';
   }
   TestItem(TestItem const& t) {
      memcpy(freak, t.freak, sizeof(freak));
      freak[12] = '\0';
      id = t.id;
   }
   TestItem const& operator=(TestItem const& t) {
      if(this == &t)
         return *this;

      memcpy(freak, t.freak, sizeof(freak));
      freak[12] = '\0';
      id = t.id;

      return *this;
   }
   virtual ~TestItem() {}

   virtual void setItemKey(int num_recs,int) { id = num_recs; }

   virtual int getSize() const { return sizeof(TestItem); }
   virtual int getItemKey() const { return id; }

   bool operator<(TestItem const& t)  const { return (id<t.id); }
   bool operator==(TestItem const& t) const {
      if( (id == t.id) &&
         (0 == strncmp((char*)freak, (char*)t.freak, sizeof(freak))) ) {
            return true;
         }
         return false;
   }

   friend std::ostream& operator<<(std::ostream & ost, TestItem const& src);

private:
   unsigned char freak [13];
   int id;
};

#define cu_assert(x) if(!(x)) std::cerr << "durn" << std::endl;

template <class T> void convert(T) {}

template <class Iterator, class ConstIterator>
void test_interactions(Iterator i, ConstIterator ci)
{
   cu_assert( i == ci );               // comparisons
   cu_assert( !(i != ci) );
   cu_assert( !(i < ci) );
   cu_assert( i <= ci );
   cu_assert( !(i > ci) );
   cu_assert( i >= ci );
   std::size_t distance = ci - i;   // difference
   cu_assert( distance == 0 );
   ci = i;                          // assignment
   ConstIterator ci2(i);            // construction
   cu_assert( ci2 == ci );
   convert<ConstIterator>(i);       // implicit conversion
}

using namespace ZUtil;

int main(int argc, char* argv[])
{
   TestItem* tr1 = new TestItem;
   tr1->setItemKey(11,11);
   TestItem* tr2 = new TestItem;
   tr2->setItemKey(22,22);

   SmartList <TestItem> sl;
   const SmartList <TestItem>& csl = sl;

   sl.append(tr1);
   sl.append(tr2);

   SmartList <TestItem>::iterator iter = sl.begin();
   SmartList <TestItem>::const_iterator c_iter = sl.begin();
   SmartList <TestItem>::rev_iterator r_iter = sl.rbegin();
   SmartList <TestItem>::const_rev_iterator c_r_iter = sl.rbegin();

   //c_iter->setItemKey(33,33);   //no compile for new
   c_r_iter->setItemKey(33,33);   //does compile for new

   test_interactions(iter, c_iter); 
   test_interactions(r_iter, c_r_iter);

   return 0;
}