#ifndef GUARD_List_h_15102006
#define GUARD_List_h_15102006
#pragma once
#include <iostream>
#include <stdexcept>
#include <string>
namespace RE {
template<typename T>
class List {
private:
/* Private list object ListNode<T>
* -------------------------------
* -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<typename T>
class ListNode {
public:
T* p_; //ptr to data being managed by node
ListNode<T>* pprev_; //ptr to previous node in sequence
ListNode<T>* 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<T>* p ) { pprev_ = p; }
void setNodeNext( ListNode<T>* p ) { pnext_ = p; }
T& getNodeValue() { return *p_; }
ListNode<T>* previous() { return pprev_; }
ListNode<T>* next() { return pnext_; }
// Overloaded operators
T& operator* () { return *p_; }
T& operator* ( ListNode<T> const& pNode ) { return *p_; }
bool operator==( ListNode<T>* pNode ) { return this->getNodeValue() == pNode->getNodeValue(); }
bool operator!=( ListNode<T>* 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 << endl;
std::cout << ".---------------------------------------------.\n";
std::cout << "| ListNode<T>* List<T>::Iterator @ 0x" << it.getNode() << " |\n";
std::cout << "|---------------------------------------------|\n";
if(hasData) std::cout << "| *p_ = " << *(it.getNode()->p_) << std::endl;
std::cout << "| p_ = 0x" << it.getNode()->p_ << " |\n";
std::cout << "| pprev_ = 0x" << it.getNode()->pprev_ << " |\n";
std::cout << "| pnext_ = 0x" << it.getNode()->pnext_ << " |\n";
std::cout << "`---------------------------------------------'\n";
}
~ListNode()
{
delete p_;
}
};
public:
/* Public List object iterator
* ---------------------------
* -Contains a pointer to a ListNode<T> for referencing node values
* Object is used to reference the values of each ListNode<T> in the List
*/
class iterator {
private:
ListNode<T>* node_; //ptr to node object in list
public:
iterator()
: node_(0)
{}
iterator( ListNode<T>* pNode )
: node_(pNode)
{}
public:
// Returns the address of the node currently pointed to
ListNode<T>* getNode() { return node_; }
// Overloaded Operators
T& operator* () { return *(*node_); }
T& operator* ( iterator const& it ) { return *(it.getNode()); }
bool operator==( iterator& it ) { return this->getNode() == it.getNode(); }
bool operator!=( iterator& it ) { return this->getNode() != it.getNode(); }
bool operator>=( iterator& it ) { return *this >= *(it.getNode()); }
bool operator<=( iterator& it ) { return *this <= *(it.getNode()); }
iterator& operator++( int ) {
if( getNode() != getNode()->next() ) {
iterator tmp;
tmp = *this;
pointMeTo( getNode()->next() );
return tmp;
}
else
return *this;
}
iterator& operator++() {
if( getNode() != getNode()->next() )
pointMeTo( getNode()->next() );
return *this;
}
iterator& operator--( int ) {
if( getode() != getNode()->previous() ) {
iterator tmp;
tmp = *this;
pointMeTo( getNode()->previous() );
return tmp;
}
else
return *this;
}
iterator& operator--() {
if( getNode() != getNode()->previous() )
pointMeTo( getNode()->previous() );
return *this;
}
// Forces the iterator to point to a new ListNode<T>
void pointMeTo( ListNode<T>* newNode ) { node_ = newNode; }
};
private:
iterator itFirst_;
iterator itLast_;
int size_;
public:
List() {
// Create a list and create a blank node as end()
ListNode<T>* newNode = new ListNode<T>;
newNode->setNodePrev( newNode );
newNode->setNodeNext( newNode );
itFirst_.pointMeTo( newNode );
itLast_.pointMeTo( newNode );
size_ = 0;
}
List( T& newVal ) {
// Create a list and create a node for newVal as begin() [blank node as end()]
ListNode<T>* newNode = new ListNode<T>;
ListNode<T>* endNode = new ListNode<T>;
newNode->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<T>* newNode = new ListNode<T>;
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<T>* newNode = new ListNode<T>;
newNode->setNodeValue( &newVal );
newNode->setNodePrev( newNode );
newNode->setNodeNext( it.getNode() );
it.getNode()->setNodePrev( newNode );
it.pointMeTo( newNode );
itFirst_ = it;
}
else {
ListNode<T>* newNode = new ListNode<T>;
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<T> list ) { return min() >= list.max(); }
bool operator<=( List<T> list ) { return max() <= list.min(); }
~List() {}
};
}
#endif
|
Register
Wiki
Blog
Search
Turing
Chat Room
Members
