DynArray.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
 * Copyright (C) 1999-2009 Fraunhofer Institute FIRST and Max-Planck-Society
 */

#ifndef _DYNARRAY_H_
#define _DYNARRAY_H_

#include <shogun/lib/common.h>
#include <shogun/lib/memory.h>
#include <shogun/mathematics/Math.h>

namespace shogun
{
template <class T> class CDynamicArray;
template <class T> class CDynamicObjectArray;

template <class T> class DynArray
{
    template<class U> friend class CDynamicArray;
    template<class U> friend class CDynamicObjectArray;
    friend class CCommUlongStringKernel;

    public:
        DynArray(int32_t p_resize_granularity=128, bool tracable=true)
        {
            this->resize_granularity=p_resize_granularity;
            use_sg_mallocs=tracable;

            if (use_sg_mallocs)
                array=SG_CALLOC(T, p_resize_granularity);
            else
                array=(T*) calloc(p_resize_granularity, sizeof(T));

            num_elements=p_resize_granularity;
            last_element_idx=-1;
        }

        virtual ~DynArray()
        {
            if (use_sg_mallocs)
                SG_FREE(array);
            else
                free(array);
        }

        inline int32_t set_granularity(int32_t g)
        {
            g=CMath::max(g,128);
            this->resize_granularity = g;
            return g;
        }

        inline int32_t get_array_size() const
        {
            return num_elements;
        }

        inline int32_t get_num_elements() const
        {
            return last_element_idx+1;
        }

        inline T get_element(int32_t index) const
        {
            return array[index];
        }

        inline T* get_element_ptr(int32_t index)
        {
            return &array[index];
        }

        inline T get_element_safe(int32_t index) const
        {
            if (index>=get_num_elements())
            {
                SG_SERROR("array index out of bounds (%d >= %d)\n",
                         index, get_num_elements());
            }
            return array[index];
        }

        inline bool set_element(T element, int32_t index)
        {
            if (index < 0)
            {
                return false;
            }
            else if (index <= last_element_idx)
            {
                array[index]=element;
                return true;
            }
            else if (index < num_elements)
            {
                array[index]=element;
                last_element_idx=index;
                return true;
            }
            else
            {
                if (resize_array(index))
                    return set_element(element, index);
                else
                    return false;
            }
        }

        inline bool insert_element(T element, int32_t index)
        {
            if (append_element(get_element(last_element_idx)))
            {
                for (int32_t i=last_element_idx-1; i>index; i--)
                {
                    array[i]=array[i-1];
                }
                array[index]=element;

                return true;
            }

            return false;
        }

        inline bool append_element(T element)
        {
            return set_element(element, last_element_idx+1);
        }

        inline void push_back(T element)
        {
            if (get_num_elements() < 0) set_element(element, 0);
            else set_element(element, get_num_elements());
        }

        inline void pop_back()
        {
            if (get_num_elements() <= 0) return;
            delete_element(get_num_elements()-1);
        }

        inline T back() const
        {
            if (get_num_elements() <= 0) return get_element(0);
            return get_element(get_num_elements()-1);
        }

        int32_t find_element(T element) const
        {
            int32_t idx=-1;
            int32_t num=get_num_elements();

            for (int32_t i=0; i<num; i++)
            {
                if (array[i] == element)
                {
                    idx=i;
                    break;
                }
            }

            return idx;
        }

        inline bool delete_element(int32_t idx)
        {
            if (idx>=0 && idx<=last_element_idx)
            {
                for (int32_t i=idx; i<last_element_idx; i++)
                    array[i]=array[i+1];

                memset(&array[last_element_idx], 0, sizeof(T));
                last_element_idx--;

                if (num_elements - last_element_idx
                    > resize_granularity)
                    resize_array(last_element_idx+1);

                return true;
            }

            return false;
        }

        bool resize_array(int32_t n)
        {
            int32_t new_num_elements= ((n/resize_granularity)+1)
                *resize_granularity;

            T* p;
            
            if (use_sg_mallocs)
                p = SG_REALLOC(T, array, new_num_elements);
            else
                p = (T*) realloc(array, new_num_elements*sizeof(T));
            if (p)
            {
                array=p;
                if (new_num_elements > num_elements)
                {
                    memset(&array[num_elements], 0,
                           (new_num_elements-num_elements)*sizeof(T));
                }
                else if (n+1<new_num_elements)
                {
                    memset(&array[n+1], 0,
                           (new_num_elements-n-1)*sizeof(T));
                }

                //in case of shrinking we must adjust last element idx
                if (n-1<last_element_idx)
                    last_element_idx=n-1;

                num_elements=new_num_elements;
                return true;
            }
            else
                return false;
        }

        inline T* get_array() const
        {
            return array;
        }

        inline void set_array(T* p_array, int32_t p_num_elements,
                              int32_t array_size)
        {
            SG_FREE(this->array);
            this->array=p_array;
            this->num_elements=array_size;
            this->last_element_idx=p_num_elements-1;
        }

        inline void clear_array()
        {
            if (last_element_idx >= 0)
                memset(array, 0, (last_element_idx+1)*sizeof(T));
        }

        void shuffle()
        {
            for (index_t i=0; i<=last_element_idx; ++i)
                CMath::swap(array[i], array[CMath::random(i, last_element_idx)]);
        }

        inline T operator[](int32_t index) const
        {
            return array[index];
        }

        DynArray<T>& operator=(DynArray<T>& orig)
        {
            resize_granularity=orig.resize_granularity;

            /* check if orig array is larger than current, create new array */
            if (orig.num_elements>num_elements)
            {
                SG_FREE(array);

                if (use_sg_mallocs)
                    array=SG_MALLOC(T, orig.num_elements);
                else
                    array=(T*) malloc(sizeof(T)*orig.num_elements);
            }

            memcpy(array, orig.array, sizeof(T)*orig.num_elements);
            num_elements=orig.num_elements;
            last_element_idx=orig.last_element_idx;

            return *this;
        }

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

    protected:
        int32_t resize_granularity;

        T* array;

        int32_t num_elements;

        int32_t last_element_idx;

        bool use_sg_mallocs;
};
}
#endif /* _DYNARRAY_H_  */