-----------------------------------

r.3volved

Tue Oct 17, 2006 7:41 pm


non-STL List Container [C++]

-----------------------------------

Any feedback would be appreciated.


#ifndef GUARD_List_h_15102006
#define GUARD_List_h_15102006
#pragma once

#include 
#include 
#include 

namespace RE {
	template
	class List {
	private:
		/* Private list object ListNode
		 * -------------------------------
		 * -Maintains a pointer to the managed data in the list
		 * -Maintains a pointer to the previous node in the series
		 * -Maintains a pointer to the next node in the series
		 */
		template
		class ListNode {
		public:
			T* p_;					//ptr to data being managed by node
			ListNode* pprev_;	//ptr to previous node in sequence
			ListNode* pnext_;	//ptr to next node in sequence

			ListNode()
				: p_( 0 )
			{}

			ListNode( T* pVal )
				: p_( pVal )
			{}

			// Set value that node is maintaining
			void setNodeValue( T* p )
			{
				T* tmp = new T;
				*tmp = *p;
				p_ = tmp;
			}
			
			void			setNodePrev( ListNode* p ) { pprev_ = p; }
			void			setNodeNext( ListNode* p ) { pnext_ = p; }			
			T&				getNodeValue() { return *p_; }
			ListNode*	previous() { return pprev_; }
			ListNode*	next() { return pnext_; }
			
			// Overloaded operators
			T&		operator* () { return *p_; }
			T&		operator* ( ListNode const& pNode ) { return *p_; }
			bool	operator==( ListNode* pNode ) { return this->getNodeValue() == pNode->getNodeValue(); }
			bool	operator!=( ListNode* pNode ) { return this->p_ == pNode->p_; }

			// Output of the ListNode at iterator position
			void outputState( iterator& it, std::string name, bool hasData = true )
			{
				std::cout setNodePrev( &newNode );
			newNode->setNodeNext( &endNode );
			newNode->setNodeValue( &newVal );

			endNode->setNodePrev( &newNode );
			endNode->setNodeNext( &endNode );

			itFirst_.pointMeTo( &newNode );
			itLast_.pointMeTo( &endNode );
			size_ = 1;
		}

		// Insert item ( Sort order smallest -> biggest )
		void insert( T newVal ) {
			if( empty() ) {
				itFirst_.getNode()->setNodeValue( &newVal );
				ListNode* newNode = new ListNode;
				newNode->setNodePrev( itFirst_.getNode() );
				newNode->setNodeNext( newNode );
				itFirst_.getNode()->setNodePrev( itFirst_.getNode() );
				itFirst_.getNode()->setNodeNext( newNode );
				itLast_.pointMeTo( newNode );
			}
			else {
				iterator it = begin();
				for( it; it != end(); ++it ) {
					if( *it >= newVal )
						break;
				}
		
				if( it == begin() ) {				// we are inserting at the first node
					ListNode* newNode = new ListNode;
					newNode->setNodeValue( &newVal );
					newNode->setNodePrev( newNode );
					newNode->setNodeNext( it.getNode() );
					it.getNode()->setNodePrev( newNode );
					it.pointMeTo( newNode );
					itFirst_ = it;
				}
				else {
					ListNode* newNode = new ListNode;
					newNode->setNodeValue( &newVal );
					newNode->setNodePrev( it.getNode()->previous() );
					newNode->setNodeNext( it.getNode() );
					it.getNode()->setNodePrev( newNode );
					it.pointMeTo( newNode->previous() );
					it.getNode()->setNodeNext( newNode );
				}
			}
			++size_;
		}

		// Remove item from list
		void remove( iterator& it )
		{
			if( it == begin() ) //we are at the beginning
			{
				iterator tmp = it;
				it.pointMeTo( tmp.getNode()->next() );
				it.getNode()->setNodePrev( it.getNode() );
				itFirst_ = it;
				destroyThis( tmp );
			}
			else if( it == end() ) //we are at the end
			{
				// We can't do anything on this node cause we're at the end
				throw std::exception("Trying to access end() in: " __FUNCTION__ );
			}
			else 
			{
				try
				{
					iterator tmp = it;
					it.pointMeTo( it.getNode()->next() );
					it.getNode()->setNodePrev( tmp.getNode()->previous() );
					it.pointMeTo( tmp.getNode()->previous() );
					it.getNode()->setNodeNext( tmp.getNode()->next() );
					destroyThis( tmp );
				}
				catch(std::exception e)
				{
					throw e;
				}
			}
			--size_;
		}

		// Destroys all the elements in List and leaves list empty
		void clear()
		{
			iterator tmp = begin();
			while( tmp != end() )
			{
				iterator destroyMe = tmp;
				tmp.pointMeTo( tmp.getNode()->next() );
				destroyThis( destroyMe );
				--size_;
			}
			itFirst_ = itLast_;
			itFirst_.getNode()->setNodeNext( itFirst_.getNode() );
			itFirst_.getNode()->setNodePrev( itFirst_.getNode() );
		}

		// Returns true if empty, otherwise false
		bool empty() { return begin() == end();	}

		// Clears list and deletes the last pointer
		void destroy()
		{
			clear();
			destroyThis( itLast_ );
		}

		T min() 
		{ 
			if( !empty() )
			{
				iterator it = begin();
				return *it; 
			}
			else
				throw std::exception("Error: List is empty[min doesn't exist yet ;)]");
		}

		T max() 
		{
			if( !empty() )
			{
				iterator it = end();
				return *(--it);
			}
			else
				throw std::exception("Error: List is empty[max doesn't exist yet ;)]");
		}

		// Destroy item in list that iterator points to
		void destroyThis( iterator& it ) { delete it.getNode(); }

		int size() { return size_; }
		iterator begin() { return itFirst_; }
		iterator end() { return itLast_; }
		// Returns an iterator to end() -1 (ie. Last value, 2nd last element)
		iterator last() 
		{
			if( !empty() )
			{
				iterator tmp = itLast_;
				return --tmp;
			}
			else throw std::exception("Error: Trying to access an empty list");
		}
		
		bool	operator>=( List list ) { return min() >= list.max(); }
		bool	operator