LinkedList.cpp

Go to the documentation of this file.

/** @file LinkedList.cpp
* @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.
* =================================================================
*/

#ifndef DREAM_LINKEDLISTCPP
#define DREAM_LINKEDLISTCPP

#include "LinkedList.h"

namespace DREAM
{

/////////////////////////////////////////////////////////////////////////////
//
// LinkedListNode
//
/////////////////////////////////////////////////////////////////////////////

template <class item_type>
LinkedListNode <item_type>::LinkedListNode (item_type item, LinkedListNode <item_type>* left) 
: item_ (item), left_ (left), right_ (NULL)
{
};

template <class item_type>
LinkedListNode <item_type>::~LinkedListNode ()
{
        if (right_)
                delete right_;
}

template <class item_type>
inline item_type LinkedListNode <item_type>::item ()
{
        return item_;
}

template <class item_type>
inline const item_type LinkedListNode <item_type>::item () const
{
        return item_;
}

template <class item_type>
inline void LinkedListNode <item_type>::item (item_type the_item)
{
        item_ = the_item;
}

template <class item_type>
inline void LinkedListNode <item_type>::left (LinkedListNode <item_type>* node_ptr)
{
        left_ = node_ptr;
}

template <class item_type>
inline void LinkedListNode <item_type>::right (LinkedListNode <item_type>* node_ptr)
{
        right_ = node_ptr;
}

template <class item_type>
LinkedListNode <item_type>& LinkedListNode <item_type>::operator= (LinkedListNode <item_type>& node)
{
        item_ = node.item_;
        left_ = node.left_;
        right_ = node.right_;
        return *this;
}

template <class item_type>
inline LinkedListNode <item_type>* LinkedListNode <item_type>::iter_next ()
{
        return right_;
}

template <class item_type>
inline LinkedListNode <item_type>* LinkedListNode <item_type>::iter_previous ()
{
        return left_;
}

template <class item_type>
inline const LinkedListNode <item_type>* LinkedListNode <item_type>::iter_next () const
{
        return right_;
}

template <class item_type>
inline const LinkedListNode <item_type>* LinkedListNode <item_type>::iter_previous () const
{
        return left_;
}

/////////////////////////////////////////////////////////////////////////////
//
// LinkedList
//
/////////////////////////////////////////////////////////////////////////////

template <class item_type>
LinkedList <item_type>::LinkedList ()
: root_ptr_ (NULL), last_ptr_ (NULL), size_ (0) {};

template <class item_type>
LinkedList <item_type>::~LinkedList ()
{
        if (root_ptr_)
                delete root_ptr_;
}

template <class item_type>
void LinkedList <item_type>::assign (const LinkedListNode <item_type>* begin_node, const LinkedListNode <item_type>* end_node)
{
        Iterator <LinkedListNode <item_type> > iter;

        for (iter = begin_node; iter != end_node; iter++)
                push_back (iter);
}


template <class item_type>
void LinkedList <item_type>::assign (Iterator <LinkedListNode <item_type> >& begin_iter, Iterator <LinkedListNode <item_type> >& end_iter)
{
        Iterator <LinkedListNode <item_type> > iter;

        for (iter = begin_iter; iter != end_iter; iter++)
                push_back (iter);
}

template <class item_type>
void LinkedList <item_type>::assign (Const_Iterator <LinkedListNode <item_type> >& begin_iter, Const_Iterator <LinkedListNode <item_type> >& end_iter)
{
        Const_Iterator <LinkedListNode <item_type> > iter;

        for (iter = begin_iter; iter != end_iter; iter++)
                push_back (iter);
}

template <class item_type>
inline LinkedListNode <item_type>* LinkedList <item_type>::begin ()
{
        return root_ptr_;
}

template <class item_type>
inline const LinkedListNode <item_type>* LinkedList <item_type>::begin () const
{
        return root_ptr_;
}

template <class item_type>
void LinkedList <item_type>::clear ()
{
        if (root_ptr_)
        {
                delete root_ptr_;
                size_ = 0;
                root_ptr_ = NULL;
        }
}

template <class item_type>
void LinkedList <item_type>::destroy ()
{
        if (root_ptr_)
        {
                Iterator <LinkedListNode <item_type> > iter;
                for (iter = begin (); iter != end (); iter++)
                        delete iter->item_;
        
                delete root_ptr_;
                size_ = 0;
                root_ptr_ = NULL;
        }
}

template <class item_type>
inline bool LinkedList <item_type>::empty ()
{
        return (size_ == 0) ? true : false;
}

template <class item_type>
inline LinkedListNode <item_type>* LinkedList <item_type>::end ()
{
        return NULL;
}

template <class item_type>
inline const LinkedListNode <item_type>* LinkedList <item_type>::end () const
{
        return NULL;
}

template <class item_type>
void LinkedList <item_type>::erase (Iterator <LinkedListNode <item_type> >& iter)
{
        LinkedListNode <item_type>* left_ptr = iter->iter_previous ();
        LinkedListNode <item_type>* right_ptr = iter->iter_next ();
        --size_;

        left_ptr->right_ = right_ptr;
        right_ptr->left_ = left_ptr;

        iter->right_ = NULL;
        delete *iter;
}

template <class item_type>
LinkedListNode <item_type>* LinkedList <item_type>::find (Iterator <LinkedListNode <item_type> >& node_iter)
{
        Iterator <LinkedListNode <item_type> > iter;

        for (iter = begin (); iter != end (); iter++)
        {
                if (iter == node_iter)
                {
                        return *iter;
                }
        }

        return NULL;
}

template <class item_type>
const LinkedListNode <item_type>* LinkedList <item_type>::find (Const_Iterator <LinkedListNode <item_type> >& node_iter) const
{
        Iterator <LinkedListNode <item_type> > iter;

        for (iter = begin (); iter != end (); iter++)
        {
                if (iter == node_iter)
                {
                        return *iter;
                }
        }

        return NULL;
}

template <class item_type>
void LinkedList <item_type>::push_back (item_type item)
{
        ++size_;

        if (!root_ptr_)
        {
                // First element
                root_ptr_ = new LinkedListNode <item_type> (item);
                last_ptr_ = root_ptr_;
        }
        else
        {
                // Append item to LinkedList
                last_ptr_->right_ = new LinkedListNode <item_type> (item, last_ptr_);
                last_ptr_ = last_ptr_->iter_next ();
        }
}

template <class item_type>
inline LinkedListNode <item_type>* LinkedList <item_type>::last ()
{
        return last_ptr_;
}

template <class item_type>
inline const LinkedListNode <item_type>* LinkedList <item_type>::last () const
{
        return last_ptr_;
}

template <class item_type>
item_type& LinkedList <item_type>::operator [] (uint i)
{
        Iterator <LinkedListNode <item_type> > iter;
        iter = begin ();

        uint j;
        for (j = 0; j < i; j++)
                ++iter;

        return *iter;
}

template <class item_type>
const item_type& LinkedList <item_type>::operator [] (uint i) const
{
        Const_Iterator <LinkedListNode <item_type> > iter;
        iter = begin ();

        uint j;
        for (j = 0; j < i; j++)
                ++iter;

        return *iter;
}

template <class item_type>
inline uint LinkedList <item_type>::size () const
{
        return size_;
}

};

#endif

---