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
 * Written (W) 2012 Heiko Strathmann
 * Copyright (C) 1999-2009 Fraunhofer Institute FIRST and Max-Planck-Society
 */

#ifndef _LIST_H_
#define _LIST_H_

#include <shogun/lib/config.h>

#include <shogun/lib/common.h>
#include <shogun/base/SGObject.h>
#include <shogun/base/Parameter.h>

namespace shogun
{
class CListElement :public CSGObject
{
    public:
        CListElement()
            : next(NULL), prev(NULL), data(NULL)
        {
            init();
        }

        CListElement(CSGObject* p_data,
                CListElement* p_prev = NULL,
                CListElement* p_next = NULL)
        {
            init();

            this->data = p_data;
            this->next = p_next;
            this->prev = p_prev;
        }

        virtual ~CListElement() { data = NULL; }

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

    private:
        void init()
        {
            m_parameters->add(&data, "data", "Data of this element.");
            m_parameters->add((CSGObject**) &next, "next",
                    "Next element in list.");
            m_model_selection_parameters->add((CSGObject**) &next, "next",
                    "Next element in list.");
            m_model_selection_parameters->add(&data, "data", "Data of this element.");
        }

    public:
        CListElement* next;
        CListElement* prev;
        CSGObject* data;

};

class CList : public CSGObject
{
    public:
        CList(bool p_delete_data=false) : CSGObject()
        {
            m_parameters->add(&delete_data, "delete_data",
                              "Delete data on destruction?");
            m_parameters->add(&num_elements, "num_elements",
                              "Number of elements.");
            m_parameters->add((CSGObject**) &first, "first",
                              "First element in list.");
            m_model_selection_parameters->add((CSGObject**) &first, "first",
                                  "First element in list.");

            first  = NULL;
            current = NULL;
            last   = NULL;

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

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

            delete_all_elements();
        }

        inline void delete_all_elements()
        {
            // move to the first element and then delete sequentially
            CSGObject* d=get_first_element();

            // important to unref because get_first_elements() SG_REFs it
            if (delete_data)
                SG_UNREF(d);

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

                // we don't need to check for delete_data flag here
                // delete_element() takes care of whether or not
                // data should be SG_UNREF'ed
            }

            first=NULL;
            current=NULL;
            last=NULL;
        }

        inline int32_t get_num_elements() { return num_elements; }

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

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

        inline CSGObject* 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 CSGObject* 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 CSGObject* get_current_element()
        {
            if (current != NULL)
            {
                if (delete_data)
                    SG_REF(current->data);
                return current->data;
            }
            else
                return NULL;
        }



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

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

        inline CSGObject* get_next_element(CListElement*& 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 CSGObject* get_previous_element(CListElement*& 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 CSGObject* get_current_element(CListElement*& 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(CSGObject* data)
        {
            SG_DEBUG("Entering\n");

            // none available, case is shattered in insert_element()
            if (current != NULL)
            {
                CSGObject* e=get_next_element();
                if (e)
                {
                    if (delete_data)
                        SG_UNREF(e);
                    // if successor exists use insert_element()
                    SG_DEBUG("Leaving\n");
                    return insert_element(data);
                }
                else
                {
                    // case with no successor but nonempty
                    CListElement* element;

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

                        num_elements++;

                        if (delete_data)
                            SG_REF(data);

                        SG_DEBUG("Leaving\n");
                        return true;
                    }
                    else
                    {
                        SG_WARNING("Error in allocating memory for new element!\n");
                        SG_DEBUG("Leaving\n");
                        return false;
                    }
                }
            }
            else
            {
                SG_DEBUG("Leaving\n");
                return insert_element(data);
            }
        }

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

            return append_element(data);
        }

        inline bool push(CSGObject* data)
        {
            return append_element_at_listend(data);
        }

        inline bool pop()
        {
            if (last)
            {
                if (first==last)
                    first=NULL;

                if (current==last)
                {
                    if (first==last)
                        current=NULL;
                    else
                        current=current->prev;
                }

                if (delete_data)
                    SG_UNREF(last->data);

                CListElement* temp=last;
                last=last->prev;
                SG_UNREF(temp);
                if (last)
                    last->next=NULL;

                num_elements--;

                return true;
            }
            else
                return false;
        }

        inline bool insert_element(CSGObject* data)
        {
            CListElement* element;

            if (delete_data)
                SG_REF(data);

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

                    num_elements++;

                    return true;
                }
                else
                {
                    SG_WARNING("Error in allocating memory for new element!\n");
                    return false;
                }
            }
            else
            {
                if ((element = new CListElement(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
                {
                    SG_WARNING("Error in allocating memory for new element!\n");
                    return false;
                }
            }
        }

        inline CSGObject* delete_element()
        {
            SG_DEBUG("Entering\n");
            CSGObject* data = current ? current->data : NULL;

            if (num_elements>0)
                num_elements--;

            if (data)
            {
                if (delete_data)
                {
                    SG_GCDEBUG("Decreasing refcount of %s(%p)!\n",
                            data->get_name(), data);
                    SG_UNREF(data);
                }

                CListElement *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;

                SG_DEBUG("Leaving\n");
                return data;
            }

            SG_DEBUG("Leaving\n");
            return NULL;
        }

        virtual void load_serializable_post() throw (ShogunException)
        {
            CSGObject::load_serializable_post();

            current = first;
            CListElement* prev = NULL;
            for (CListElement* cur=first; cur!=NULL; cur=cur->next)
            {
                cur->prev = prev;
                prev = cur;
            }
            last = prev;
        }

        void print_list()
        {
            CListElement* c=first;

            while (c)
            {
                SG_PRINT("\"%s\" at %p\n", c->data ? c->data->get_name() : "", c->data)
                c=c->next;
            }
        }

        inline bool get_delete_data() { return delete_data; }

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

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