LinkedList.h

Go to the documentation of this file.

/** @file LinkedList.h
* @author Gabor Madl
* @date Created 10/2006
* @brief Doubly linked list template class.
*
*
* =================================================================
* DREAM License v2.0
* 
* DREAM - Distributed Real-time Embedded Analysis Method
* http://dre.sourceforge.net.
* Copyright (c) 2005-2007 Gabor Madl, All Rights Reserved.
* 
* This file is part of DREAM.
* 
* DREAM is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation. No future versions of
* the GPL license may be automatically applied to DREAM. It is in
* the sole discretion of the copyright holder to determine whether
* DREAM may be released under a different license or terms. There
* are no restrictions on the use of DREAM for any purpose.
* 
* DREAM is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* 
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
* 
* By submitting comments, suggestions, code, code snippets,
* techniques (including that of usage), and algorithms, submitters
* acknowledge that they have the right to do so, that any such
* submissions are given freely and unreservedly, and that they
* waive any claims to copyright or ownership. In addition,
* submitters acknowledge that any such submission might become
* part of the copyright maintained on the overall body of code,
* which comprises DREAM. By making a submission, submitter agrees
* to these terms. Furthermore, submitters acknowledge that the
* incorporation or modification of such submissions is entirely
* at the discretion of the moderators of the DREAM project.
* 
* DREAM links to the Libxml2 third party library. Please see 
* COPYING-libxml for the copyright information of Libxml2.
* =================================================================
*/

#if (_MSC_VER >= 1400)                          // VC8+
#pragma warning (disable:4996)          // Disable all deprecation warnings
#endif 

#ifndef DREAM_LINKEDLIST
#define DREAM_LINKEDLIST

/** Unsigned int type definition.
* Redefining the basic type allows easy portability to 8 or 16 bit machines. 
*/
typedef unsigned int uint;
#define maxuint 4294967295

#include "Iterator.h"
#include "Iterator.cpp"

namespace DREAM
{

template <class item_type> class LinkedList;

/** Struct for one element in the LinkedList. */
template <class item_type>
class LinkedListNode
{
// friend class declarations and typedefs confuse Doxygen... Starting with protected members first.
protected:
        /** ++ operator. 
        * This operator does not actually change the node's value and should only be used from within Iterators.
        */
        LinkedListNode <item_type>* iter_next ();

        /** -- operator. 
        * This operator does not actually change the node's value and should only be used from within Iterators.
        */
        LinkedListNode <item_type>* iter_previous ();

        /** ++ operator. 
        * This operator does not actually change the node's value and should only be used from within Iterators.
        */
        const LinkedListNode <item_type>* iter_next () const;

        /** -- operator. 
        * This operator does not actually change the node's value and should only be used from within Iterators.
        */
        const LinkedListNode <item_type>* iter_previous () const;

        /** The left child of the node. */
        LinkedListNode <item_type>* left_;
        
        /** The right child of the node. */
        LinkedListNode <item_type>* right_;

        /** The item of the node. */
        item_type item_;

public:
        /** Constructor. */
        LinkedListNode (item_type item, LinkedListNode <item_type>* left = NULL);

        /** Destructor. */
        ~LinkedListNode ();

        /** Returns the item of the node. */
        item_type item ();

        /** Returns the item of the node. */
        const item_type item () const;

        /** Sets the item of the node. */
        void item (item_type the_item);

        /** Sets the left child of the node. */
        void left (LinkedListNode <item_type>* node_ptr);

        /** Sets the right child of the node. */
        void right (LinkedListNode <item_type>* node_ptr);

        /** Assignment operator */
        LinkedListNode <item_type>& operator= (LinkedListNode <item_type>& node);

        /** Allow iterators to manipulate protected members. */
        friend class Iterator <LinkedListNode <item_type> >;

        /** Allow iterators to manipulate protected members. */
        friend class Const_Iterator <LinkedListNode <item_type> >;

        /** Allow LinkedList to manipulate protected members. */
        friend class LinkedList <item_type>;
};



/** This class implements a doubly linked list. */
template <class item_type>
class LinkedList
{
// friend class declarations and typedefs confuse Doxygen... Starting with protected members first.
protected:
        /** Pointer to the first element of the linked list. */
        LinkedListNode <item_type>* root_ptr_;

        /** Pointer to the last element of the linked list. */
        LinkedListNode <item_type>* last_ptr_;

        /** Stores the number of items in the AVLTree. */
        uint size_;

public:
        /** Constructor. */
        LinkedList ();

        /** Destructor. */
        ~LinkedList ();

        /** Assign operator. */
        void assign (const LinkedListNode <item_type>* begin_node, const LinkedListNode <item_type>* end_node);

        /** Assign operator. */
        void assign (Iterator <LinkedListNode <item_type> >& begin_iter, Iterator <LinkedListNode <item_type> >& end_iter);

        /** Assign operator. */
        void assign (Const_Iterator <LinkedListNode <item_type> >& begin_iter, Const_Iterator <LinkedListNode <item_type> >& end_iter);

        /** Returns a pointer to the smallest element in the LinkedList. */
        LinkedListNode <item_type>* begin ();

        /** Returns a pointer to the smallest element in the LinkedList. */
        const LinkedListNode <item_type>* begin () const;

        /** Erases elements in the LinkedList. */
        void clear ();

        /** Erases elements in the LinkedList, and calls delete on the item_type.
        * Use this function whenever you would like to iterate through the LinkedList, and erase dynamically allocated data.
        */
        void destroy ();

        /** Returns true if the LinkedList is empty. */
        bool empty ();

        /** Returns NULL. */
        LinkedListNode <item_type>* end ();

        /** Returns NULL. */
        const LinkedListNode <item_type>* end () const;

        /** Erase a node from the LinkedList. */
        void erase (Iterator <LinkedListNode <item_type> >& iter);

        /** Finds a LinkedList node in the LinkedList. */
        LinkedListNode <item_type>* find (Iterator <LinkedListNode <item_type> >& node_iter);

        /** Finds a LinkedList node in the LinkedList. */
        const LinkedListNode <item_type>* find (Const_Iterator <LinkedListNode <item_type> >& node_iter) const;

        /** Insert a LinkedList node in the LinkedList. */
        void push_back (item_type item);

        /** Returns a pointer to the last element in the LinkedList. */
        LinkedListNode <item_type>* last ();

        /** Returns a pointer to the last element in the LinkedList. */
        const LinkedListNode <item_type>* last () const;

        /** operator [].*/
        item_type& operator [] (uint i);

        /** operator [].*/
        const item_type& operator [] (uint i) const;

        /** Return the number of items in the LinkedList. */
        uint size () const;

        /** iterator class for convenience. */
        typedef Iterator <LinkedListNode <item_type> > iterator;

        /** const_iterator class for convenience. */
        typedef Const_Iterator <LinkedListNode <item_type> > const_iterator;

        /** Allow iterators to manipulate protected members. */
        friend class Iterator <LinkedListNode <item_type> >;

        /** Allow iterators to manipulate protected members. */
        friend class Const_Iterator <LinkedListNode <item_type> >;
};

};

#endif

---