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
 * Copyright (C) 2012 Engeniy Andreev (gsomix)
 */

#ifndef _DYNARRAY_H_
#define _DYNARRAY_H_

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

namespace shogun
{
template <class T> class CDynamicArray;

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

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

            if (use_sg_mallocs)
                array=SG_MALLOC(T, p_resize_granularity);
            else
                array=(T*) malloc(size_t(p_resize_granularity)*sizeof(T));

            num_elements=p_resize_granularity;
            current_num_elements=0;
        }

        DynArray(T* p_array, int32_t p_array_size, bool p_free_array, bool p_copy_array, bool tracable=true)
        {
            resize_granularity=p_array_size;
            free_array=false;
            use_sg_mallocs=tracable;

            array=NULL;
            set_array(p_array, p_array_size, p_array_size, p_free_array, p_copy_array);
        }

        DynArray(const T* p_array, int32_t p_array_size, bool tracable=true)
        {
            resize_granularity=p_array_size;
            free_array=false;
            use_sg_mallocs=tracable;

            array=NULL;
            set_array(p_array, p_array_size, p_array_size);
        }

        virtual ~DynArray()
        {
            if (array!=NULL && free_array)
            {
                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 current_num_elements;
        }

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

        inline T get_last_element() const
        {
            return array[current_num_elements-1];
        }

        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 <= current_num_elements-1)
            {
                array[index]=element;
                return true;
            }
            else if (index < num_elements)
            {
                array[index]=element;
                current_num_elements=index+1;
                return true;
            }
            else
            {
                if (free_array && 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(current_num_elements-1)))
            {
                for (int32_t i=current_num_elements-2; 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, current_num_elements);
        }

        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<=current_num_elements-1)
            {
                for (int32_t i=idx; i<current_num_elements-1; i++)
                    array[i]=array[i+1];

                current_num_elements--;

                if (num_elements - current_num_elements - 1
                    > resize_granularity)
                    resize_array(current_num_elements);

                return true;
            }

            return false;
        }

        bool resize_array(int32_t n, bool exact_resize=false)
        {
            int32_t new_num_elements=n;
            
            if (!exact_resize)
            {
                new_num_elements=((n/resize_granularity)+1)*resize_granularity;
            }

            T* p;

            if (use_sg_mallocs)
                p = SG_REALLOC(T, array, num_elements, new_num_elements);
            else
                p = (T*) realloc(array, new_num_elements*sizeof(T));

            if (p || new_num_elements==0)
            {
                array=p;

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

                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 p_array_size, bool p_free_array, bool p_copy_array)
        {
            if (array!=NULL && free_array)
                SG_FREE(array);

            if (p_copy_array)
            {
                if (use_sg_mallocs)
                    array=SG_MALLOC(T, p_array_size);
                else
                    array=(T*) malloc(p_array_size*sizeof(T));
                memcpy(array, p_array, p_array_size*sizeof(T));
            }
            else
                array=p_array;

            num_elements=p_array_size;
            current_num_elements=p_num_elements;
            free_array=p_free_array;
        }

        inline void set_array(const T* p_array, int32_t p_num_elements,
                              int32_t p_array_size)
        {
            if (array!=NULL && free_array)
                SG_FREE(array);

            if (use_sg_mallocs)
                array=SG_MALLOC(T, p_array_size);
            else
                array=(T*) malloc(p_array_size*sizeof(T));
            memcpy(array, p_array, p_array_size*sizeof(T));

            num_elements=p_array_size;
            current_num_elements=p_num_elements;
            free_array=true;
        }

        inline void clear_array(T value)
        {
            if (current_num_elements-1 >= 0)
            {
                for (int32_t i=0; i<current_num_elements; i++)
                    array[i]=value;
            }
        }

        void reset(T value)
        {
            clear_array(value);
            current_num_elements=0;
        }

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

        void shuffle(CRandom * rand)
        {
            for (index_t i=0; i<=current_num_elements-1; ++i)
                CMath::swap(array[i], array[rand->random(i, current_num_elements-1)]);
        }

        void set_const(const T& const_element)
        {
            for (int32_t i=0; i<num_elements; i++)
                array[i]=const_element;
        }

        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;
            current_num_elements=orig.current_num_elements;

            return *this;
        }

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

    protected:
        int32_t resize_granularity;

        T* array;

        int32_t num_elements;

        int32_t current_num_elements;

        bool use_sg_mallocs;

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