ds.doublylinkedlist.h

// doubly linked list
#pragma once
#include "common.h"
#include "ds.singlylinkedlist.h"
#include <string>
using namespace std;

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


namespace yasi{
namespace ds{


	// doubly linked list interface
	template<class E, class Node, class Iter = DLLIterator<E,Node> >
	class IDoublyLinkedList : public virtual ISinglyLinkedList < E, Node, Iter > 
	{
	public:
		virtual ~IDoublyLinkedList(){};
		virtual Node* tail() const = 0;
		virtual Node* addBack(const E&) = 0;
		virtual void pushFront(const E&) = 0;
		virtual void pushBack(const E&) = 0;
		virtual void popFront() = 0;
		virtual void popBack() = 0;
		virtual const E& back() const = 0;
	};

	// doubly linked list iterator
	template<class E, class Node>
	class DLLIterator : public virtual BidirectionalNodeIterator< E, Node, DLLIterator<E,Node> > {
		typedef DLLIterator<E, Node> self;
		typedef BidirectionalNodeIterator< E, Node, DLLIterator<E, Node> > base;
	public:
		virtual ~DLLIterator(){}
		DLLIterator() {}
		DLLIterator(Node* pNode) : IteratorBase(pNode){}
		DLLIterator(const base& other) : IteratorBase(other.pNode){}
		self& operator=(const self& other){ pNode = other.pNode; return *this; }
		virtual self operator ++ (int){ self temp(this->pNode); incr();  return temp; }
		virtual self operator -- (int){ self temp(this->pNode); decr();  return temp; }
		virtual self& operator ++ (){ incr();  return *this; }
		virtual self& operator -- (){ decr();  return *this; }
		//virtual E& operator*(){ if (pNode) return pNode->element; }
	};

	// doubly linked list class
	template<class E, class Node = DListNode<E>, class Iter = DLLIterator<E,Node> >
	class DoublyLinkedList :public virtual IDoublyLinkedList < E, Node, Iter >, // implements interface
							public virtual SinglyLinkedList<E, Node, Iter> { // inherits singly-linked list
		////////// enable testing ////////////////
		FRIEND_TEST_CLASS(DoublyLinkedListTest);

		typedef SinglyLinkedList<E, Node> base;

	protected:
		// typedefs
		typedef Node node_t;
	public:
		typedef DLLIterator<E, Node> iterator;
		typedef node_t NodeType;
	protected:

		// new members
		//node_t* pTail;

		// make the list circular, so that we can make the iterator end()
		// tail-->horizon-->head


		node_t* before(node_t* pNode) override{
			if (pNode) return pNode->prev();
			else return NULL;
		}
		virtual node_t* tail()const override{ return (_size == 0) ? NULL : end().pNode->prev(); }

	public:
		typedef DLLIterator<E, Node> iterator;
		typedef node_t NodeType;

		// parent methods/variables

		/////// constructor/destructor ///////////
		DoublyLinkedList(){
			// make a unit circle: horizon--horizon--horizon
			pHorizon->setPrev(pHorizon);
		}
		DoublyLinkedList(const E* srcArr, const int numElems) : DoublyLinkedList() {
			fromArray(srcArr, numElems);
		}
		~DoublyLinkedList(){
			this->clear();
		}
		/////////////////////////////////////////////////////////////
		//////////// Implement IDoubleLinkedList methods ////////////
		/////////////////////////////////////////////////////////////
		// Inherited from SinglyLinkedList
		// Node* head() = 0; 

		// Inherited from SinglyLinkedList
		// int size() const = 0;

		// Inherited from SinglyLinkedList
		// bool elements(E**, int&) = 0;

		// Inherited from SinglyLinkedList
		// void toString(string&) = 0;
		////////////////////////////////////////
		/////////// IList methods //////////////
		////////////////////////////////////////
		void pushFront(const E& e) override{
			this->addFront(e);
		}
		void pushBack(const E& e) override{
			this->addBack(e);
		}
		void popFront() override{
			this->remove(head());
		}
		void popBack() override{
			this->remove(tail());
		}
		inline const E& back() const  override{
			if (size() > 0)
				return tail()->element;
			else
				return _defaultElem;
		}

		////////////// iterators /////////////
		// need to redefine because DLLIterator
		// is different from SLLIterator

		virtual bool empty() const{ return (begin() == end()) && _size == 0; }
		virtual node_t* addFront(const E& e) {
			return insert(begin(), e);
			//node_t* pNode = new node_t(e, pHead, NULL); // pNode->next = pHead
			//if (pHead != NULL) pHead->setPrev(pNode);
			//pHead = pNode;
			//if (pTail == NULL) pTail = pNode;
			//_size++;
			//return pNode; 
		}
		virtual node_t* addBack(const E& e){
			return insert(end(), e);
			//node_t* pNode = new node_t(e, NULL, pTail); // pNode->prev = pTail
			//if (pTail != NULL) pTail->setNext(pNode);
			//pTail = pNode;
			//if(pHead == NULL) pHead = pNode;
			//_size++;
			//return pNode;
		}
		virtual node_t* addBefore(const E& e, node_t* pAfter) {
			if (pAfter)
				return insert(pAfter, e);
			else
				return NULL;

			//if (pAfter == NULL) return NULL;

			//if (pAfter == pHead)
			//	return addFront(e); // add before head

			//node_t* pBefore = before(pAfter);
			//if (pBefore){
			//	node_t* pNode = new node_t(e, pAfter, pBefore); // dynamic memory allocation
			//	pBefore->setNext(pNode);
			//	pAfter->setPrev(pNode);
			//	_size++;
			//	return pNode;
			//}
			//else return NULL;
		}
		virtual node_t* addAfter(const E& e, node_t* pBefore){
			if (pBefore)
				return insert(pBefore->next(), e);
			else
				return NULL;

			//if (pBefore == NULL) return NULL;

			//if (pBefore == pTail)
			//	return addBack(e); // add after tail

			//node_t* pAfter = pBefore->next();
			//if (pAfter){
			//	node_t* pNode = new node_t(e, pAfter, pBefore); // dynamic memory allocation
			//	pBefore->setNext(pNode);
			//	pAfter->setPrev(pNode);
			//	_size++;
			//	return pNode;
			//}
			//else return NULL;
		}
		
		// inserts the element e at the specified position
		node_t* insert(iterator here, const E& e = E()){
			//		before--here.............. would become
			//		before--newnode--here
			node_t* pBefore = here.pNode->prev();
			node_t* pHere = here.pNode;
			node_t* pNewNode = new node_t(e, pHere, pBefore); // before<--newnode-->here
			pBefore->setNext(pNewNode); // before-->newnode
			pHere->setPrev(pNewNode); // newnode<--here

			_size++;

			// finally
			return pNewNode;
		}
		
		virtual bool remove(node_t* pNode, E& e) {
			// cannot remove the pHorizon or the NULL node
			if (pNode == NULL || pNode == pHorizon) return false;

			e = pNode->element;
			// removing from the middle
			node_t* pAfter = pNode->next();
			node_t* pBefore = pNode->prev();
			// pBefore and pAfter must be non-null
			if (pBefore && pAfter){
				pBefore->setNext(pAfter);
				pAfter->setPrev(pBefore);
				_size--;
				DELETE_SAFE(pNode); // free memory
				return true;
			}
			else{
				// something is wrong; pNode may not be in the list
				return false;
			}
		}
		virtual bool remove(node_t* pNode) {
			E e;
			return remove(pNode, e);
		}
		virtual void clear(){
			for (iterator n = begin(); n != end(); ){
				node_t* pNode = (n++).pNode;
				DELETE_SAFE(pNode);
			}
			_size = 0;
			pHorizon->setNext(pHorizon);
			pHorizon->setPrev(pHorizon);
		}
	};

	// override for printing
	template<class E, class Node = DListNode<E>, class Iter = DLLIterator<E, Node> >
	std::ostream& operator<< (std::ostream& out, const DoublyLinkedList<E, Node, Iter>& list) {
		out << list.toString();
		return out;
	}
	template<class E, class Node = DListNode<E>, class Iter = DLLIterator<E, Node> >
	std::ostream& operator<< (std::ostream& out, const DoublyLinkedList<E, Node, Iter>* pList) {
		out << pList->toString();
		return out;
	}



} // namespace ds

} // namespace yasi