List.h

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Written (W) 1999-2009 Soeren Sonnenburg
 * Written (W) 1999-2008 Gunnar Raetsch
 * Copyright (C) 1999-2009 Fraunhofer Institute FIRST and Max-Planck-Society
 */

#ifndef _LIST_H_
#define _LIST_H_

#include "lib/common.h"
#include "base/SGObject.h"

namespace shogun
{
template <class T> class CListElement
{
    public:
        CListElement* next;
        CListElement* prev;
        T data;

    public:
        CListElement(T p_data, CListElement* p_prev = NULL, CListElement* p_next = NULL)
        {
            this->data = p_data;
            this->next = p_next;
            this->prev = p_prev;
        };

        virtual ~CListElement() { data = NULL; }
};

template <class T> class CList : public CSGObject
{
    public:
        CList(bool p_delete_data=false) : CSGObject()
        {
            first  = NULL;
            current = NULL;
            last   = NULL;

            num_elements = 0;
            this->delete_data=p_delete_data;
        }

        virtual ~CList()
        {
            SG_DEBUG("Destroying List %p\n", this);

            while (get_num_elements())
            {
                T d=delete_element();

                if (delete_data)
                {
                    SG_DEBUG("Destroying List Element %p\n", d);
                    SG_UNREF(d);
                }
            }
        }

        inline int32_t get_num_elements() { return num_elements; }

        inline T get_first_element()
        {
            if (first != NULL)
            {
                current = first;
                if (delete_data)
                    SG_REF(current->data);
                return current->data;
            }
            else 
                return NULL;
        }

        inline T get_last_element()
        {
            if (last != NULL)
            {
                current = last;
                if (delete_data)
                    SG_REF(current->data);
                return current->data;
            }
            else 
                return NULL;
        }

        inline T get_next_element()
        {
            if ((current != NULL) && (current->next != NULL))
            {
                current = current->next;
                if (delete_data)
                    SG_REF(current->data);
                return current->data;
            }
            else
                return NULL;
        }

        inline T get_previous_element()
        {
            if ((current != NULL) && (current->prev != NULL))
            {
                current = current->prev;
                if (delete_data)
                    SG_REF(current->data);
                return current->data;
            }
            else
                return NULL;
        }

        inline T get_current_element()
        {
            if (current != NULL)
            {
                if (delete_data)
                    SG_REF(current->data);
                return current->data;
            }
            else 
                return NULL;
        }



        inline T get_first_element(CListElement<T> *&p_current)
        {
            if (first != NULL)
            {
                p_current = first;
                if (delete_data)
                    SG_REF(p_current->data);
                return p_current->data;
            }
            else
                return NULL;
        }

        inline T get_last_element(CListElement<T> *&p_current)
        {
            if (last != NULL)
            {
                p_current = last;
                if (delete_data)
                    SG_REF(p_current->data);
                return p_current->data;
            }
            else
                return NULL;
        }

        inline T get_next_element(CListElement<T> *& p_current)
        {
            if ((p_current != NULL) && (p_current->next != NULL))
            {
                p_current = p_current->next;
                if (delete_data)
                    SG_REF(p_current->data);
                return p_current->data;
            }
            else
                return NULL;
        }

        inline T get_previous_element(CListElement<T> *& p_current)
        {
            if ((p_current != NULL) && (p_current->prev != NULL))
            {
                p_current = p_current->prev;
                if (delete_data)
                    SG_REF(p_current->data);
                return p_current->data;
            }
            else
                return NULL;
        }

        inline T get_current_element(CListElement<T> *& p_current)
        {
            if (p_current != NULL)
            {
                if (delete_data)
                    SG_REF(p_current->data);
                return p_current->data;
            }
            else 
                return NULL;
        }

        inline bool append_element(T data)
        {
            if (current != NULL)    // none available, case is shattered in insert_element()
            {
                T e=get_next_element();
                if (e)
                {
                    if (delete_data)
                        SG_UNREF(e);
                    // if successor exists use insert_element()
                    return insert_element(data);
                }
                else
                {
                    // case with no successor but nonempty
                    CListElement<T>* element;

                    if ((element = new CListElement<T>(data, current)) != NULL)
                    {
                        current->next = element;
                        current       = element;
                        last         = element;

                        num_elements++;

                        if (delete_data)
                            SG_REF(data);

                        return true;
                    }
                    else
                        return false;
                }
            }
            else
                return insert_element(data);
        }

        inline bool append_element_at_listend(T data)
        {
            T p = get_last_element();
            if (delete_data)
                SG_UNREF(p);

            return append_element(data);
        }

        inline bool insert_element(T data)
        {
            CListElement<T>* element;

            if (delete_data)
                SG_REF(data);

            if (current == NULL)
            {
                if ((element = new CListElement<T> (data)) != NULL)
                {
                    current = element;
                    first  = element;
                    last   = element;

                    num_elements++;

                    return true;
                }
                else
                    return false;
            }
            else
            {
                if ((element = new CListElement<T>(data, current->prev, current)) != NULL)
                {
                    if (current->prev != NULL)
                        current->prev->next = element;
                    else
                        first = element;

                    current->prev = element;
                    current       = element;

                    num_elements++;

                    return true;
                }
                else
                    return false;
            }
        }

        inline T delete_element(void)
        {
            T data = get_current_element();

            if (data)
            {
                if (delete_data)
                    SG_UNREF(data);

                CListElement<T> *element = current;

                if (element->prev)
                    element->prev->next = element->next;

                if (element->next)
                    element->next->prev = element->prev;

                if (element->next)
                    current = element->next;
                else
                    current = element->prev;

                if (element == first)
                    first = element->next;

                if (element == last)
                    last  = element->prev;

                delete element;

                num_elements--;

                return data;
            } 

            return NULL;
        }

        inline virtual const char* get_name() const { return "List"; }

    private:
        bool delete_data;
        CListElement<T>* first;
        CListElement<T>* current;
        CListElement<T>* last;
        int32_t num_elements;
};
}
#endif