ds.singlylinkedlist.h

#pragma once
#include "common.h"
#include "utils.h"
#include "ds.list.h"
#include "ds.node.h"
#include "ds.iterator.h"
#include <string>
using namespace std;

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

namespace yasi{

namespace ds{



// singly linked list interface
template<class E, class Node, class Iter >
class ISinglyLinkedList:virtual public IList<E, Iter>{
public:
	virtual ~ISinglyLinkedList(){}
	virtual Node* head() const = 0;
	virtual Node* addFront(const E& e) = 0;
	virtual Node* addAfter(const E&, Node*) = 0;
	virtual Node* addBefore(const E&, Node*) = 0;
	virtual bool remove(Node*, E& e) = 0;
	virtual bool remove(Node*) = 0;
	virtual void elements(E**) = 0;
	virtual string toString() const = 0;
	virtual const E& front() const = 0;
};


// singly linked list iterator
// iterator
template< class E, class Node>
class SLLIterator : public ForwardNodeIterator<E, Node, SLLIterator<E,Node> >{
	typedef SLLIterator<E, Node> self;
	typedef ForwardNodeIterator<E, Node, SLLIterator<E, Node> > base;
protected:
public:
	virtual ~SLLIterator(){ }
	SLLIterator() {}
	SLLIterator(Node* pNode) : IteratorBase(pNode){}
	SLLIterator(const self& other) : IteratorBase(other.pNode){}
	self& operator=(const self& other){ pNode = other.pNode; return *this; }
};


// singly linke list class
// virtual inheritance needed because
//	(1) the IDoublyLinkedList will also inherit from ISinglyLinkedList, and 
//	(2) DoublyLinkedList will inherit from SinglyLinkedList
template<class E, class Node = SListNode<E>, class Iter = SLLIterator<E, Node> >
class SinglyLinkedList : public virtual ISinglyLinkedList < E, Node, Iter > {
	///////////////// enable testing////////////////
	FRIEND_TEST_CLASS(SinglyLinkedListTest);

protected:
	// typedefs
	typedef Node node_t;
	typedef Iter iterator;

	//node_t* pHead; // should be obsolete
	// make the list circular, so that we can make the iterator end()
	node_t* pHorizon; // (last element)-->horizon-->head

	
	int _size;

	E _defaultElem;


	// returns the node p such that pNode = p->next()
	// it is virtual because we will allow DoublyLinkedList to override this method
	virtual node_t* before(node_t* pNode){
		if (pNode == NULL ){
			return NULL;
		}
		else{
			// start from the horizon
			node_t* pParent = pHorizon;
			while (pParent != NULL &&
				pParent->next() != pNode){
				pParent = pParent->next();
			}
			// either found, or not
			if (pParent == NULL){
				// list exhausted
				// something wrong, maybe this node is not in the list
				return NULL;
			}
			else{
				return pParent;
			}
		}
	}
	virtual node_t* head() const override{
		if (_size == 0) return NULL;
		else{
			return pHorizon->next();
		}
	}

public:
	// typedef SLLIterator<E, Node> iterator;
	SinglyLinkedList():_size(0){
		//pHead = NULL;
		pHorizon = new node_t();
		pHorizon->setNext(pHorizon); // unit loop: horizon--horizon--horizon
	}
	SinglyLinkedList(const E* pArr, const int numElems) : SinglyLinkedList(){
		//pHead = NULL;
		fromArray(pArr, numElems);
	}
	virtual ~SinglyLinkedList(){
		this->clear();
		DELETE_SAFE(pHorizon);
	}

	/////////////////////////////////////////////////////////////
	//////////// Implement ISinglyLinkedList methods ////////////
	/////////////////////////////////////////////////////////////
	virtual node_t* addFront(const E& e) override{
		return addAfter(e, pHorizon);
		// node_t* pNode = new node_t(e); // dynamic memory allocation
		//if (head() == NULL){
		//	// add the first node
		//	head() = pNode; // set at head
		//	_size = 1;
		//}
		//else{
		//	// add it before the head
		//	pNode->setNext(head());
		//	head() = pNode;
		//	_size++;
		//}
		//return pNode;
	}
	virtual node_t* addAfter(const E& e, node_t* pBefore) override{
		if (pBefore == NULL) return NULL;

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

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

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


	virtual bool remove(node_t* pNode, E& e) override{
		if (pNode == NULL || pNode == pHorizon) return false;

		e = pNode->element;
		// removing from the middle
		node_t* pAfter = pNode->next();
		node_t* pBefore = before(pNode);
		// pBefore should be non-null
		if (pBefore){
			pBefore->setNext(pAfter);
			_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) override{
		E e;
		return remove(pNode, e);
	}

	// actually, it never returns false
	// the order of elements are the reverse of the order they were inserted
	// *ppArr must contain enough memory
	void elements(E** ppArr) override{
		int i = 0;
		for (iterator n = begin(); n != end(); n++){
			(*ppArr)[i++] = *n;
		}
	}
	string toString() const override{
		std::stringstream buf;
		for (iterator n = begin(); n != end(); n++){
			buf << *n << "->";
		}
		return buf.str();
	}

	//////////// Done Implementing ISinglyLinkedList methods ////////////

	////////////////////////////////////////
	/////////// IList methods //////////////
	////////////////////////////////////////
	inline int size() const override{
		return _size;
	}
	inline bool empty() const override{
		return _size == 0 && (pHorizon == pHorizon->next() );
	}
	virtual void push(const E& e) override{
		this->addFront(e);
	}
	virtual void pop() override{
		if(size() > 0 )
			this->remove(begin().pNode);
	}
	virtual inline const E& top() const override{
		return *begin();
	}
	virtual inline const E& front() const override{
		return top();
	}

	///////////// iterators /////////////
	iterator begin() const{
		return pHorizon->next();
	}
	iterator end() const{
		return pHorizon;
	}



	///// non-interface methods
	// actually, it never returns false
	// the order of elements are the same as their insertion order
	// *ppArr must contain enough memory
	virtual void relements(E** ppArr) {
		int i = size() - 1;
		for (iterator n = begin(); n != end(); n++){
			E e = *n;
			(*ppArr)[i] = e;
			i--;
		}
	}
	void clear(){
		iterator e = end();
		for (iterator n = begin(); n != end(); ){
			node_t* pNode = (n++).pNode;
			DELETE_SAFE(pNode);
		}
		_size = 0;
		pHorizon->setNext(pHorizon);
		//pHead = NULL;
	}

	virtual bool fromArray(const E* pArr, const int numElems){
		if (!pArr || (numElems <= 0)) return false;
		
		if( !empty() ) clear();
		for (int i = 0; i < numElems; i++){
			addFront(pArr[i]);
		}
		_size = numElems; // set the size
		return true;
	}


};

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

} // namespace ds
} // namespace yasi