DynamicArray.h

/*
 * 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 _DYNAMIC_ARRAY_H_
#define _DYNAMIC_ARRAY_H_

#include <shogun/lib/config.h>

#include <deque>
#include <shogun/base/Parameter.h>
#include <shogun/base/SGObject.h>

namespace shogun
{
/** @brief Template Dynamic array class that creates an array that can
 * be used like a list or an array.
 *
 * It grows and shrinks dynamically, while elements can be accessed
 * via index.  It is performance tuned for simple types like float
 * etc. and for hi-level objects only stores pointers, which are not
 * automagically SG_REF'd/deleted.
 */
template <class T> class CDynamicArray :public CSGObject
{
	public:
		/** default constructor */
		CDynamicArray() : CSGObject()
		{
			dim1_size=1;
			dim2_size=1;
			dim3_size=1;
			num_elements = 0;
			m_array = std::deque<T>();
			init();
		}

		/** constructor
		 *
		 * @param p_dim1_size dimension 1
		 * @param p_dim2_size dimension 2
		 * @param p_dim3_size dimension 3
		 */
		CDynamicArray(
		    int32_t p_dim1_size, int32_t p_dim2_size = 1,
		    int32_t p_dim3_size = 1)
		    : CSGObject()
		{
			dim1_size=p_dim1_size;
			dim2_size=p_dim2_size;
			dim3_size=p_dim3_size;
			num_elements = 0;
			m_array = std::deque<T>(p_dim1_size * p_dim2_size * p_dim3_size);
			init();
		}

		/** constructor
		 *
		 * @param p_array another array
		 * @param p_dim1_size dimension 1
		 * @param p_free_array if array must be freed
		 * @param p_copy_array if array must be copied
		 */
		CDynamicArray(T* p_array, int32_t p_dim1_size) : CSGObject()
		{
			dim1_size=p_dim1_size;
			dim2_size=1;
			dim3_size=1;
			num_elements = p_dim1_size;
			m_array.assign(p_array, p_array + p_dim1_size);
			init();
		}

		/** constructor
		 *
		 * @param p_array another array
		 * @param p_dim1_size dimension 1
		 * @param p_dim2_size dimension 2
		 * @param p_free_array if array must be freed
		 * @param p_copy_array if array must be copied
		 */
		CDynamicArray(T* p_array, int32_t p_dim1_size, int32_t p_dim2_size)
		    : CSGObject()
		{
			dim1_size=p_dim1_size;
			dim2_size=p_dim2_size;
			dim3_size=1;
			num_elements = p_dim1_size * p_dim2_size;
			m_array.assign(p_array, p_array + p_dim1_size * p_dim2_size);
			init();
		}

		/** constructor
		 *
		 * @param p_array another array
		 * @param p_dim1_size dimension 1
		 * @param p_dim2_size dimension 2
		 * @param p_dim3_size dimension 3
		 * @param p_free_array if array must be freed
		 * @param p_copy_array if array must be copied
		 */
		CDynamicArray(
		    T* p_array, const int32_t p_dim1_size, const int32_t p_dim2_size,
		    const int32_t p_dim3_size)
		    : CSGObject()
		{
			dim1_size=p_dim1_size;
			dim2_size=p_dim2_size;
			dim3_size=p_dim3_size;
			num_elements = p_dim1_size * p_dim2_size * p_dim3_size;
			m_array.assign(
			    p_array, p_array + (p_dim1_size * p_dim2_size * p_dim3_size));
			init();
		}

		/** constructor
		 *
		 * @param p_array another array
		 * @param p_dim1_size dimension 1
		 * @param p_dim2_size dimension 2
		 * @param p_dim3_size dimension 3
		 */
		CDynamicArray(
		    const T* p_array, int32_t p_dim1_size = 1, int32_t p_dim2_size = 1,
		    int32_t p_dim3_size = 1)
		    : CSGObject()
		{
			dim1_size=p_dim1_size;
			dim2_size=p_dim2_size;
			dim3_size=p_dim3_size;
			num_elements = p_dim1_size * p_dim2_size * p_dim3_size;
			m_array.assign(
			    p_array, p_array + (p_dim1_size * p_dim2_size * p_dim3_size));
			init();
		}

		virtual ~CDynamicArray() {}

		/** get array size (including granularity buffer)
		 *
		 * @return total array size
		 */
		inline int32_t get_array_size()
		{
			return m_array.size();
		}

		/** return 2d array size
		 *
		 * @param dim1 dimension 1 will be stored here
		 * @param dim2 dimension 2 will be stored here
		 */
		inline void get_array_size(int32_t& dim1, int32_t& dim2)
		{
			dim1=dim1_size;
			dim2=dim2_size;
		}

		/** return 3d array size
		 *
		 * @param dim1 dimension 1 will be stored here
		 * @param dim2 dimension 2 will be stored here
		 * @param dim3 dimension 3 will be stored here
		 */
		inline void get_array_size(int32_t& dim1, int32_t& dim2, int32_t& dim3)
		{
			dim1=dim1_size;
			dim2=dim2_size;
			dim3=dim3_size;
		}

		/** get dimension 1
		 *
		 * @return dimension 1
		 */
		inline int32_t get_dim1() { return dim1_size; }

		/** get dimension 2
		 *
		 * @return dimension 2
		 */
		inline int32_t get_dim2() { return dim2_size; }

		/** get dimension 3
		 *
		 * @return dimension 3
		 */
		inline int32_t get_dim3() { return dim3_size; }

		/** get number of elements
		 *
		 * @return number of elements
		 */
		inline int32_t get_num_elements() const
		{
			return num_elements;
		}

		/** get array element at index
		 *
		 * @param idx1 index 1
		 * @param idx2 index 2
		 * @param idx3 index 3
		 * @return array element at index
		 */
		inline const T& get_element(int32_t idx1, int32_t idx2=0, int32_t idx3=0) const
		{
			return m_array.at(idx1 + dim1_size * (idx2 + dim2_size * idx3));
		}

		/** get array element at index
		 *
		 * @param idx1 index 1
		 * @param idx2 index 2
		 * @param idx3 index 3
		 * @return array element at index
		 */
		inline const T& element(int32_t idx1, int32_t idx2=0, int32_t idx3=0) const
		{
			return get_element(idx1, idx2, idx3);
		}

		/** get array element at index
		 *
		 * @param idx1 index 1
		 * @param idx2 index 2
		 * @param idx3 index 3
		 * @return array element at index
		 */
		inline T& element(int32_t idx1, int32_t idx2=0, int32_t idx3=0)
		{
			return m_array.at(idx1 + dim1_size * (idx2 + dim2_size * idx3));
		}

		/** get element of given array at given index
		 *
		 * @param p_array another array
		 * @param idx1 index 1
		 * @param idx2 index 2
		 * @param idx3 index 3
		 * @return array element at index
		 */
		inline T& element(T* p_array, int32_t idx1, int32_t idx2=0, int32_t idx3=0)
		{
			ASSERT(idx1>=0 && idx1<dim1_size)
			ASSERT(idx2>=0 && idx2<dim2_size)
			ASSERT(idx3>=0 && idx3<dim3_size)
			return p_array[idx1+dim1_size*(idx2+dim2_size*idx3)];
		}

		/** get element of given array at given index
		 *
		 * @param p_array another array
		 * @param idx1 index 1
		 * @param idx2 index 2
		 * @param idx3 index 3
		 * @param p_dim1_size size of dimension 1
		 * @param p_dim2_size size of dimension 2
		 * @return element of given array at given index
		 */
		inline T& element(T* p_array, int32_t idx1, int32_t idx2, int32_t idx3, int32_t p_dim1_size, int32_t p_dim2_size)
		{
			ASSERT(p_dim1_size==dim1_size)
			ASSERT(p_dim2_size==dim2_size)
			ASSERT(idx1>=0 && idx1<p_dim1_size)
			ASSERT(idx2>=0 && idx2<p_dim2_size)
			ASSERT(idx3>=0 && idx3<dim3_size)
			return p_array[idx1+p_dim1_size*(idx2+p_dim2_size*idx3)];
		}

		/** gets last array element
		 *
		 * @return array element at last index
		 */
		inline T get_last_element() const
		{
			return m_array.back();
		}

		/** get array element at index
		 *
		 * (does bounds checking)
		 *
		 * @param index index
		 * @return array element at index
		 */
		inline T get_element_safe(int32_t index) const
		{
			return m_array.at(index);
		}

		/** set array element at index
		 *
		 * @param e element to set
		 * @param idx1 index 1
		 * @param idx2 index 2
		 * @param idx3 index 2
		 * @return if setting was successful
		 */
		inline void
		set_element(T e, int32_t idx1, int32_t idx2 = 0, int32_t idx3 = 0)
		{
			m_array[idx1 + dim1_size * (idx2 + dim2_size * idx3)] = e;
		}

		/** insert array element at index
		 *
		 * @param e element to insert
		 * @param index index
		 * @return if setting was successful
		 */
		inline bool insert_element(T e, int32_t index)
		{
			try
			{
				m_array.insert(m_array.begin() + index, e);

				num_elements++;
				return true;
			}
			catch (const std::bad_alloc&)
			{
				return false;
			}
		}

		/** append array element to the end of array
		 *
		 * @param e element to append
		 * @return if setting was successful
		 */
		inline void append_element(T e)
		{
			m_array.push_back(e);
			num_elements++;
		}

		/** STD VECTOR compatible. Append array element to the end
		 *  of array.
		 *
		 * @param e element to append
		 */
		inline void push_back(T e)
		{
			m_array.push_back(e);
			num_elements++;
		}

		/** STD VECTOR compatible. Delete array element at the end
		 *  of array.
		 */
		inline void pop_back()
		{
			m_array.pop_back();
			num_elements--;
		}

		/** STD  VECTOR compatible. Return array element at the end
		 *  of array.
		 *
		 * @return element at the end of array
		 */
		inline T back()
		{
			return m_array.back();
		}

		/** find first occurence of array element and return its index
		 * or -1 if not available
		 *
		 * @param e element to search for
		 * @return index of element or -1
		 */
		inline int32_t find_element(T e)
		{
			auto it = std::find(m_array.begin(), m_array.end(), e);
			if (it == m_array.end())
			{
				return -1;
			}
			else
			{
				auto index = std::distance(m_array.begin(), it);
				return int32_t(index);
			}
		}

		/** delete array element at idx
		 * (does not call SG_FREE() or the like)
		 *
		 * @param idx index
		 * @return if deleting was successful
		 */
		inline bool delete_element(int32_t idx)
		{
			int32_t old_length = m_array.size();
			m_array.erase(m_array.begin() + idx);
			if (old_length > int32_t(m_array.size()))
			{
				num_elements--;
				return true;
			}
			else
			{
				return false;
			}
		}

		/** resize array
		 *
		 * @param ndim1 new dimension 1
		 * @param ndim2 new dimension 2
		 * @param ndim3 new dimension 3
		 * @return if resizing was successful
		 */
		inline void
		resize_array(int32_t ndim1, int32_t ndim2 = 1, int32_t ndim3 = 1)
		{
			dim1_size=ndim1;
			dim2_size=ndim2;
			dim3_size=ndim3;
			m_array.resize(ndim1 * ndim2 * ndim3);
		}

		/** set array with a constant */
		void set_const(const T& const_element)
		{
			std::fill(m_array.begin(), m_array.end(), const_element);
		}

		/** get the array
		 * call get_array just before messing with it DO NOT call any
		 * [],resize/delete functions after get_array(), the pointer may
		 * become invalid !
		 *
		 * @return the array
		 */
		inline T* get_array()
		{
			auto it = m_array.begin();
			return &(*it);
		}

		/** set the 3d array pointer and free previously allocated memory
		 *
		 * @param p_array another array
		 * @param dim1 dimension 1
		 * @param dim2 dimension 2
		 * @param dim3 dimension 3
		 * @param p_free_array if array must be freed
		 * @param copy_array if array must be copied
		 */
		inline void
		set_array(T* p_array, int32_t dim1, int32_t dim2 = 1, int32_t dim3 = 1)
		{
			dim1_size=dim1;
			dim2_size=dim2;
			dim3_size=dim3;
			m_array.assign(p_array, p_array + dim1 * dim2 * dim3);
		}

		/** set the array pointer and free previously allocated memory
		 *
		 * @param p_array another array
		 * @param p_size size of another array
		 */
		inline void set_array(const T* p_array, int32_t p_size)
		{
			m_array.assign(p_array, p_array + p_size);
		}

		/** clear the array (with e.g. zeros)
		 * @param value value to fill array with
		 */
		inline void clear_array(T value)
		{
			std::fill(m_array.begin(), m_array.end(), 0);
		}

		/** resets the array */
		inline void reset_array()
		{
			num_elements = 0;
			std::fill(m_array.begin(), m_array.end(), 0);
		}

		/** operator overload for array read only access
		 * use set_element() for write access (will also make the array
		 * dynamically grow)
		 *
		 * DOES NOT DO ANY BOUNDS CHECKING
		 *
		 * @param index index
		 * @return element at index
		 */
		inline const T& operator[](int32_t index) const
		{
			return get_element(index);
		}

		/** operator overload for array read-write access
		 *
		 * DOES NOT DO ANY BOUNDS CHECKING
		 *
		 * @param index index
		 * @return element at index
		 */
		inline T& operator[](int32_t index)
		{
			return m_array.at(index);
		}

		/** operator overload for array assignment
		 *
		 * @param orig original array
		 * @return new array
		 */
		inline CDynamicArray<T>& operator=(CDynamicArray<T>& orig)
		{
			m_array=orig.m_array;
			dim1_size=orig.dim1_size;
			dim2_size=orig.dim2_size;
			dim3_size=orig.dim3_size;
			num_elements = orig.num_elements;

			return *this;
		}

		/** shuffles the array (not thread safe!) */
		inline void shuffle()
		{
			std::random_shuffle(m_array.begin(), m_array.end());
		}

		/** shuffles the array with external random state */
		// inline void shuffle(CRandom * rand) { m_array.shuffle(rand); }

		/** display this array */
		inline void display_array()
		{
			if (get_name())
				SG_PRINT("DynamicArray '%s' of size: %dx%dx%d\n", get_name(), dim1_size, dim2_size, dim3_size)
			else
				SG_PRINT("DynamicArray of size: %dx%dx%d\n",dim1_size, dim2_size, dim3_size)

			for (int32_t k=0; k<dim3_size; k++)
				for (int32_t i=0; i<dim1_size; i++)
				{
					SG_PRINT("element(%d,:,%d) = [ ",i, k)
					for (int32_t j=0; j<dim2_size; j++)
						SG_PRINT("%1.1f,", (float32_t) element(i,j,k))
					SG_PRINT(" ]\n")
				}
		}

		/** display array's size */
		inline void display_size()
		{
			SG_PRINT("DynamicArray of size: %dx%dx%d\n",dim1_size, dim2_size, dim3_size)
		}

		/** @return object name */
		virtual const char* get_name() const
		{
			return "DynamicArray";
		}

		/** Can (optionally) be overridden to pre-initialize some member
		 *  variables which are not PARAMETER::ADD'ed.  Make sure that at
		 *  first the overridden method BASE_CLASS::LOAD_SERIALIZABLE_PRE
		 *  is called.
		 *
		 *  @exception ShogunException Will be thrown if an error
		 *                             occurres.
		 */
		virtual void load_serializable_pre() throw (ShogunException)
		{
			CSGObject::load_serializable_pre();

			m_array.resize(num_elements);
		}

		/** Can (optionally) be overridden to pre-initialize some member
		 *  variables which are not PARAMETER::ADD'ed.  Make sure that at
		 *  first the overridden method BASE_CLASS::SAVE_SERIALIZABLE_PRE
		 *  is called.
		 *
		 *  @exception ShogunException Will be thrown if an error
		 *                             occurres.
		 */
		virtual void save_serializable_pre() throw (ShogunException)
		{
			CSGObject::save_serializable_pre();
			m_array.resize(num_elements);
		}

		virtual CSGObject* clone()
		{
			CDynamicArray * cloned = (CDynamicArray*) CSGObject::clone();
			// Since the array vector is registered with
			// current_num_elements as size (see parameter
			// registration) the cloned version has less memory
			// allocated than known to dynarray. We fix this here.
			// cloned->m_array.num_elements =
			// cloned->m_array.current_num_elements;
			return cloned;
		}

	private:

		/** register parameters */
		virtual void init()
		{
			set_generic<T>();

			SG_ADD(
			    &num_elements, "num_elements",
			    "The number of elements of array", MS_NOT_AVAILABLE);
			SG_ADD(&dim1_size, "dim1_size", "Dimension 1", MS_NOT_AVAILABLE);
			SG_ADD(&dim2_size, "dim2_size", "Dimension 2", MS_NOT_AVAILABLE);
			SG_ADD(&dim3_size, "dim3_size", "Dimension 3", MS_NOT_AVAILABLE);
		}

	protected:

		/** underlying array */
		std::deque<T> m_array;

		/** number of elements */
		int32_t num_elements;

		/** dimension 1 */
		int32_t dim1_size;

		/** dimension 2 */
		int32_t dim2_size;

		/** dimension 3 */
		int32_t dim3_size;
};
}
#endif /* _DYNAMIC_ARRAY_H_  */