DynamicArray.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 "lib/common.h"
#include "lib/Mathematics.h"
#include "base/SGObject.h"

namespace shogun
{
template <class T> class CDynamicArray : public CSGObject
{
    public:
        CDynamicArray(int32_t p_resize_granularity=128)
        : CSGObject()
        {
            this->resize_granularity=p_resize_granularity;

            array=(T*) calloc(p_resize_granularity, sizeof(T));
            ASSERT(array);

            num_elements=p_resize_granularity;
            last_element_idx=-1;
        }

        virtual ~CDynamicArray() { 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()
        {
            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_safe(int32_t index) const
        {
            if (index>=get_num_elements())
            {
                SG_ERROR("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);
        }

        int32_t find_element(T element)
        {
            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];

                array[last_element_idx]=0;
                last_element_idx--;

                if ( num_elements - last_element_idx >= resize_granularity)
                    resize_array(last_element_idx);

                return true;
            }

            return false;
        }

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

            T* p= (T*) realloc(array, sizeof(T)*new_num_elements);
            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()
        {
            return array;
        }

        inline void set_array(T* p_array, int32_t p_num_elements, int32_t array_size)
        {
            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));
        }

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

        CDynamicArray<T>& operator=(CDynamicArray<T>& orig)
        {
            resize_granularity=orig.resize_granularity;
            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 "DynamicArray"; }

    protected:
        int32_t resize_granularity;

        T* array;

        int32_t num_elements;

        int32_t last_element_idx;
};
}
#endif