ds.iterator.h

#pragma once
#include "common.h"
#include "utils.h"
#include "ds.node.h"

using namespace std;

/******** enable-disable testing *******/
#include "test.this.module.h"


namespace yasi{
	namespace ds{

		template<	class Elem, 
					class Iterated, 
					class Iterator >
		class IteratorBase{
			////////////////// enable testing ////////////////
			FRIEND_TEST_CLASS(IteratorTest);

			typedef IteratorBase<Elem,Iterated,Iterator> self;
		protected:
			// this is protected because child classes use `Node' as
			// template argument passed as `Iterated' in this base class
			typedef Iterated Node;
		public:
			// a member of items that are iterated through
			Iterated* pNode;

			virtual ~IteratorBase(){ pNode = NULL; }
			IteratorBase() : pNode(NULL){}
			IteratorBase(Node* pNode) : pNode(pNode){}
			IteratorBase(const self& other) : pNode(other.pNode){}
			//IteratorBase(const IteratorBase<Elem, Iterated, Iterator>& other) : pNode(other.pNode){}
			// operators
			virtual Elem& operator* () const = 0;

			virtual bool operator == (const self& other) const { return this->pNode == other.pNode; }
			virtual bool operator != (const self& other) const { return this->pNode != other.pNode; }
			self& operator=(const self& other){ pNode = other.pNode; return *this; }
		};

		// forward iterator
		template<	class E, 
					class Iterated,
					class Iterator >
		class ForwardIterator :public virtual IteratorBase<E,Iterated,Iterator>{
			////////////////// enable testing ////////////////
			FRIEND_TEST_CLASS(IteratorTest);

			typedef IteratorBase<E, Iterated, Iterator> base;
			typedef ForwardIterator<E,Iterated,Iterator> self;
		protected:
			// children must implement their increment method
			virtual void incr() = 0;
		public:
			virtual ~ForwardIterator(){}
			ForwardIterator(){}
			ForwardIterator(Iterated* pNode) :IteratorBase(pNode){}
			ForwardIterator(const self& other) :IteratorBase(other.pNode){}
			self& operator ++ (){ incr();  return self(pNode); }
			//virtual self operator ++ (int){ self temp(this->pNode); incr();  return temp; }
			self& operator=(const self& other){ pNode = other.pNode; return *this; }
		};

		// backward iterator
		template<	class E, 
					class Iterated,
					class Iterator>
		class BackwardIterator :public virtual IteratorBase<E,Iterated,Iterator>{
			////////////////// enable testing ////////////////
			FRIEND_TEST_CLASS(IteratorTest);

			typedef IteratorBase<E, Iterated, Iterator> base;
			typedef BackwardIterator<E, Iterated, Iterator> self;
		protected:
			// children must implement their decrement method
			virtual void decr() = 0;
		public:
			virtual ~BackwardIterator(){}
			BackwardIterator(){}
			BackwardIterator(Iterated* pNode) :IteratorBase(pNode){}
			BackwardIterator(const self& other) :IteratorBase(other.pNode){}
			self& operator -- (){ decr();  return *this; }
			//self& operator -- (int){ self temp = *this; decr();  return temp; }
			//virtual self operator -- (int){ self temp(this->pNode); decr();  return temp; }
			self& operator=(const self& other){ pNode = other.pNode; return *this; }
		};

		// bidirectional iterator
		template<	class E,
			class Iterated,
			class Iterator
		>
		class BidirectionalIterator :
				public virtual ForwardIterator<E, Iterated, Iterator>,
				public virtual BackwardIterator<E, Iterated, Iterator>{
			////////////////// enable testing ////////////////
			FRIEND_TEST_CLASS(IteratorTest);

			typedef ForwardIterator<E, Iterated, Iterator> base1;
			typedef BackwardIterator<E, Iterated, Iterator> base2;
			typedef BidirectionalIterator<E, Iterated, Iterator> self;
		protected:
			// children must implement their increment/decrement method
		public:
			virtual ~BidirectionalIterator(){}
			BidirectionalIterator(){}
			BidirectionalIterator(Iterated* pNode) :IteratorBase(pNode){}
			BidirectionalIterator(const self& other) :IteratorBase(other.pNode){}
			self& operator=(const self& other){ pNode = other.pNode; return *this; }
		};



		// node iterator base
		template<class E, class Node, class Iterator>
		class NodeIteratorBase : public virtual ForwardIterator<E, Node, Iterator>{
			////////////////// enable testing ////////////////
			FRIEND_TEST_CLASS(IteratorTest);

			typedef ForwardIterator<E, Node, Iterator> base;
			typedef NodeIteratorBase<E,Node,Iterator> self;
		protected:
		public:
			virtual ~NodeIteratorBase(){}

			NodeIteratorBase() : ForwardIterator(){}
			NodeIteratorBase(Node* pNode) : IteratorBase(pNode){}
			NodeIteratorBase(const self& other) : IteratorBase(other.pNode){}
			// operators
			// if the pNode is NULL, behavior is undefined
			virtual E& operator* () const override { 
				E e;  
				if (pNode) 
					return pNode->element; 
				else 
					// undefined behavior
					// in MSVC, disable warning "returning address of local variable or temporary"
#ifdef _MSC_VER
# pragma warning( push )
# pragma warning( disable:4172)
#endif
					return e;
#ifdef _MSC_VER
# pragma warning( pop )
#endif
			}
			self& operator=(const self& other){ pNode = other.pNode; return *this; }

		};

		// forward node iterator
		// class Node must have next() method and `element' public member
		template<class E, class Node, class Iterator > // E is the value type
		class ForwardNodeIterator : public NodeIteratorBase<E, Node,Iterator >{
			////////////////// enable testing ////////////////
			FRIEND_TEST_CLASS(IteratorTest);

			typedef NodeIteratorBase<E, Node, Iterator > base;
			typedef ForwardNodeIterator<E, Node, Iterator> self;
		protected:
			virtual void incr() override{ pNode = pNode->next(); }
		public:
			virtual ~ForwardNodeIterator(){ }

			ForwardNodeIterator() {}
			ForwardNodeIterator(Node* pNode) : IteratorBase(pNode){}
			ForwardNodeIterator(const self& other) : IteratorBase(other.pNode){}
			// operators
			//virtual E& operator* () const { return pNode->element; };
			self& operator = (const self& other){ this->pNode = other.pNode; return *this; }
			self operator ++ (int){ 
				self temp(this->pNode); 
				incr();  
				return temp; 
			}
			self& operator ++ (){ incr();  return *this; }
		};

		// bidirectional node iterator
		// class Node must support prev() and next() methods and `element' public member
		template<class E, class Node, class Iterator > // E is the value type
		class BidirectionalNodeIterator :
			public virtual NodeIteratorBase<E, Node, Iterator >, 
			public virtual BidirectionalIterator<E,Node, Iterator>{

			////////////////// enable testing ////////////////
			FRIEND_TEST_CLASS(IteratorTest);

			typedef NodeIteratorBase<E, Node, Iterator > base;
			typedef ForwardIterator<E, Node, Iterator > base1; // for virtual inheritance
			typedef BackwardIterator<E, Node, Iterator > base2; // for virtual inheritance
			typedef BidirectionalNodeIterator<E, Node, Iterator> self;
		protected:
			virtual void incr() override{ pNode = pNode->next(); }
			virtual void decr() override{ pNode = pNode->prev(); }
		public:
			virtual ~BidirectionalNodeIterator(){ }

			BidirectionalNodeIterator() {}
			BidirectionalNodeIterator(Node* pNode) : IteratorBase(pNode){}
			BidirectionalNodeIterator(const self& other) : IteratorBase(other.pNode){}
			// operators
			self operator ++ (int){ self temp(this->pNode); incr();  return temp; }
			self operator -- (int){ self temp(this->pNode); decr();  return temp; }
			self& operator ++ (){ incr();  return *this; }
			self& operator -- (){ decr();  return *this; }
			self& operator = (const self& other){ this->pNode = other.pNode; return *this; }
		};



	} // namespace ds
} // namespace yasi