#ifndef LOGNGROWTH_ARRAY_IMPL_H__
#define LOGNGROWTH_ARRAY_IMPL_H__

#include "Common.h"
#include <cmath>

namespace Arrays {

template <typename T>
struct LogNGrowthArrayImpl {
	// The following static constants are defined outside the class
	// for compiler compatibility
    static const size_type FIRST_ROW_SIZE;
    static const size_type INITIAL_NUM_ROWS;

    LogNGrowthArrayImpl(const size_type initial_size);
    ~LogNGrowthArrayImpl();

    T& element(const size_type pos);
    const T& element(const size_type pos) const
        { return const_cast<LogNGrowthArrayImpl&>(*this).element(pos); }

    void swap(LogNGrowthArrayImpl& other) throw();
    void fill_from(const LogNGrowthArrayImpl& other);
    void grow(const size_type new_size);

    size_type size_; // reported array size ( <= allocated size )
    size_type last_; // last accessible array element (allocated size - 1)
    size_type content_;
	DynamicArray<T*> rows_;

private:
    // helper calculation functions

	// power of 2 using a helper array for quick calculation
	static unsigned int pow2(const unsigned int power)
	{
		static unsigned int pow2_arr[] = 
		{
			1,2,4,8,16,32,64,128,256,512,
			1024,2048,4096,8192,16384,32768,65536,131072,262144,
			524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,
			268435456,536870912,1073741824,2147483648,
		};
		static size_type pow2_arr_size = sizeof(pow2_arr) / sizeof(pow2_arr[0]);
		if (power < pow2_arr_size)
		{
			return pow2_arr[power];
		}
		return (unsigned int) pow(2.0, power);
	}

    // row of an element
    static size_type element_row(const size_type pos) 
    { 
        return (size_type) floor(log2(pos/FIRST_ROW_SIZE + 1)); 
    }

    // column of an element
    static size_type element_column(const size_type pos, const size_type row)
    { 
        return (size_type) (pos - FIRST_ROW_SIZE * (pow2(row)-1)); 
    }
    
    // log with base 2
    static double log2(const double x) 
    {
        static const double div = log(2.0);
        return log(x)/div;
    }

    // number of elements allocated in a row
    static size_type row_num_elements(const size_type row)
    {
        return (size_type) (FIRST_ROW_SIZE * pow2(row));
    }

    // number of allocated rows, according to last possible position
    static size_type num_allocated_rows(const size_type last_pos)
    {
        return element_row(last_pos) + 1;
    }

    // number of required rows including empty ones 
    // (next power of 2 from num_allocated_rows())
    static size_type num_required_rows(const size_type last_pos)
    {
        return (size_type) pow2(ceil(log2(num_allocated_rows(last_pos))));
    }

private:
    // Do not allow copies
    LogNGrowthArrayImpl(const LogNGrowthArrayImpl&);
    LogNGrowthArrayImpl& operator=(const LogNGrowthArrayImpl&);
};

// The following constants are defined here for compiler compatibility
template <typename T> 
    const size_type LogNGrowthArrayImpl<T>::FIRST_ROW_SIZE = 4;

template <typename T> 
    const size_type LogNGrowthArrayImpl<T>::INITIAL_NUM_ROWS = 2;


template <typename T>
LogNGrowthArrayImpl<T>::LogNGrowthArrayImpl(const size_type initial_size) 
    : size_(max(initial_size, FIRST_ROW_SIZE)), 
	  // sum number of elements
	  last_((size_type) (FIRST_ROW_SIZE*(pow2(num_allocated_rows(size_-1)) - 1) - 1)), 
	  content_(0),
	  rows_(max(num_required_rows(size_-1), INITIAL_NUM_ROWS))
{
    for (size_type curr_row=0; 
         curr_row < num_allocated_rows(last_); 
         ++curr_row)
    {
        try {
            rows_[curr_row] = new T[row_num_elements(curr_row)];
        } catch (...) {
            // in case T's constructor throws an exception, all 
            // memory allocated by now must be freed before 
            // rethrowing the exception
            for (size_type row_release=0; 
                 row_release<curr_row; 
                 ++row_release)
            {
                delete[] rows_[row_release];
            }
            throw;
        }
    }
}

template <typename T>
LogNGrowthArrayImpl<T>::~LogNGrowthArrayImpl()
{
    for (size_type i=0; i<num_allocated_rows(last_); ++i)
        delete[] rows_[i];
}
template <typename T>
T& LogNGrowthArrayImpl<T>::element(const size_type pos) 
{
    const size_type row = element_row(pos);
    const size_type col = element_column(pos, row);

    return rows_[row][col];
}

template <typename T>
void LogNGrowthArrayImpl<T>::swap(LogNGrowthArrayImpl& other) throw()
{
    using std::swap; // hides this function, but it's ok
    
    swap(rows_, other.rows_);
    swap(last_, other.last_);
    swap(num_rows_, other.num_rows_);
    swap(size_, other.size_);
    swap(content_, other.content_);
}

template <typename T>
void LogNGrowthArrayImpl<T>::fill_from(const LogNGrowthArrayImpl& other)
{
    content_ = 0;
    while (content_ < other.content_)
    {
        element(content_) = other.element(content_);
        ++content_;
    }
}

template <typename T>
void LogNGrowthArrayImpl<T>::grow(const size_type new_size)
{
    const size_type last_elem = new_size - 1;

    while (last_ < last_elem)
    {
        const size_type new_row = num_allocated_rows(last_);
        const size_type num_new_elements = row_num_elements(new_row);
        rows_[new_row] = new T[num_new_elements];
        last_ += num_new_elements;
    }

    size_ = new_size;
}


}

#endif