/*  ncblock.h  by K.Tsuru  */
/***************************************************************
NCBlock template class
Defined an array class of variable size for non class object.
The array has a size of power of two.
Diffrent from SNBlock class the memcpy() and memset() functions are
used.
[Notice for using double]
You must test that all elements are equal to zero or not by use of
clear() function.

[reference]
 R.B.Murray "C++ Strategies and Tactics"
****************************************************************/
#ifndef NC_BLOCK_H
#define NC_BLOCK_H 1

#include <stdio.h>
#include <assert.h>
#include <limits.h>
#include <string.h>     // for memset
#include <algorithm>    // for min() and max() since ver 2.19
#include <new>          // version 2.20
using namespace std;    // ver. 2.19

void OutOfMemory(); // defined in smanager.cpp

#ifndef TYPEDEF_H
#include "typedef.h"
#endif
// Maximum value of index.
// #ifndef INDEX_MAX
// #define INDEX_MAX (uint)INT_MAX  // = 2,147,483,647 in 32bit system
// #endif

// Return a minimum integer 2^p which satisfies sz <= 2^p.
uint ceilpow2(uint sz);

    // Minmum size.
    const uint NCBlockMinSize = 2u; // ver.2.17

template <class T> class NCBlock{
    public:
        enum ErrorType { NORMAL = 0, NULL_COPY };
    protected:
        ErrorType error ;       // error infomation
        uint    n_elements;     // number of elements
        T* elements;            // pointer of elements
    // copy function for operator=()
        void copy_block(const NCBlock<T>& a);
    // free memory
    // Use size(0,0) in non member function.
        void mem_free(){
            delete[] elements;  elements = NULL;  n_elements = 0;
        }
    public:
    /**************************************************************************
    Change the size of array.
     If sz == 0, free the memory.
    When copy > 0, copy the old elements to lower region of new array. Upper
    elements are initialized by zero.
    When copy == 0, initialize all elements by zero.
    When copy < 0, does not copy nor initialize.
    Return a really allocated size of power of two.
    **************************************************************************/
        uint    size(uint sz, int copy);
    /*************************************************************************
    Allocate greater than or equal (n + 1) elements(enlarge only) i.e.
    n-th elements is substitutable. When  n >= n_elements, double the size.
    Copy the old elements to lower region and not initialize the upper region.
    If the required memory was allocated return a value one, else zero.
    *************************************************************************/
        bool reserve(uint n);

    // clear array : for(i = from; i < min(to+1, n_elements); i++) elements[i] = 0;
        uint clear(uint from = 0, uint to = INT_MAX);
    // constructor
    // Default constructor does not allocate memory.
        NCBlock():error(NORMAL), n_elements(0), elements(NULL){}

    // constructor by size. If init_val == 0, initialize by 0.
        NCBlock(uint n_elem, int init_val = 0);
    // copy constructor
        NCBlock(const NCBlock<T>& a);
    // destructor
        virtual ~NCBlock();
        uint    size() const { return n_elements;   }

    // Element access, lhs is available
        T&  operator[](uint index){
#ifndef NDEBUG
    if(index >= n_elements){// In debuging, inline expanding switch must be off
                            // to catch the place where error occured.
        fprintf(stderr, "index = [%u], n_elements = %u\n", index, n_elements);
    assert(index < n_elements);
        exit(-1);
    }
#endif
        return elements[index];
    }

    // Element access, rhs only
        const T& operator()(uint index) const {
#ifndef NDEBUG
    if(index >= n_elements){
        fprintf(stderr, "index = (%u), n_elements = %u\n", index, n_elements);
        assert(index < n_elements);
        exit(-1);
    }
#endif
        return elements[index];
    }

        ErrorType Error() {
            ErrorType er = error;
            error = NORMAL;     // reset error
            return er;
        }

        NCBlock<T>& operator=(const NCBlock<T>& a){
            copy_block(a);  return *this;
        }
    /***************************************************************************
     The speed to access the elements by operator[] or operator() is slow, then
    implement a member function which enables us to access via the first address
    of elements.
    [Notice]
     1. Use this function below the line of size(sz, copy) or reserve().
     2. Get the array size by the function size().
    ***************************************************************************/
        T* Elements(){  return elements;    } // ver. 2.17
};
    // constructor by size.
    template <class T> NCBlock<T>::NCBlock(uint n_elem, int init_val)
    : error(NORMAL), n_elements(0), elements(NULL){
        if(n_elem) size(n_elem, (init_val > 0) ? -1 : 0);
    }

    template <class T> bool NCBlock<T>::reserve(uint index){
        if(index < n_elements) return true; // already allocated

        uint new_sz = ceilpow2(index);
        if( new_sz == index ) new_sz *= 2u;
        size(new_sz, 1);
        return error == NORMAL; // ver. 2.17
    }

    template <class T> uint NCBlock<T>::size(uint sz, int copy){
        if(!sz){    mem_free(); return 0;   }
    // new size
        uint new_sz = max( ceilpow2(sz), NCBlockMinSize);

        if( new_sz == n_elements ){ // The size is same.
            if(!copy) clear();
            return new_sz;
        }

        if(copy < 0) mem_free();// Old elements is not nessesary.
#if 1   // It does not appear warning : uninitialized. version 2.20
        T* new_ele = new T[new_sz];

        if(new_ele == NULL) OutOfMemory(); // ver. 2.17
#else
        T* new_ele;
        try {   // version 2.20
            new_ele = new T[new_sz];
        }
            catch(bad_alloc){
            OutOfMemory();
        }
#endif
        // copy
        uint n_copy = 0;
        if(copy > 0){
            n_copy = min(new_sz, n_elements);
            memcpy(new_ele, elements, n_copy*sizeof(T));
        }
/* No effect warning : uninitialized.
        // else {
        //  memset(new_ele, 0, new_sz*sizeof(T));
        // }
*/
        delete[] elements;
    /***
     Let clear() function know the elements and n_elements values.
     I cannot remove "warning uninitialized" on gcc 4.6.2.
    ***/
        elements = new_ele;
        n_elements = new_sz;
        if(copy >= 0) clear(n_copy);    // initialize the upper region by zero
        return n_elements;
    }
    // copy function for operator=()
    template <class T> void NCBlock<T>::copy_block(const NCBlock<T>& a){
        if( this == &a ) return;    // for a = a
        error = a.error;
        if(n_elements && !a.n_elements) error = NULL_COPY;  // Try to copy null.
                                                // no error for n_elements = 0
        if(error != NORMAL) return;
    // allocate memory without initialization
        if(size(a.size(), -1) == 0) return;
    // copy
#ifndef NDEBUG
    assert(a.n_elements == n_elements);
#endif
        memcpy(elements, a.elements, n_elements*sizeof(T));
    }
    // copy constructor
    template <class T> inline NCBlock<T>::NCBlock(const NCBlock<T>& a)
    :error(a.error), elements( new T[n_elements = a.n_elements] ){

        if(elements == NULL) OutOfMemory(); // ver. 2.17
        memcpy(elements, a.elements, n_elements*sizeof(T));
    }
    /************************************************************
     Initialize between elements[from] and elements[to] by zero.
     default : from = 0, to = INT_MAX
    *************************************************************/
    template <class T> uint NCBlock<T>::clear(uint from, uint to){
        uint  t = (to + 1u) < n_elements ? (to + 1u) : n_elements;  // ver. 2.17
//      uint  t = min(to +1u, n_elements);
        uint sz = (t > from) ? (t - from) : 0;
        if(!sz) return 0;   // No error when n_elements = 0 or from > to.

        T* f = &elements[from];
        memset(f, 0, sz*sizeof(T));
        return sz;
    }
    // destructor
    template <class T> NCBlock<T>::~NCBlock(){
        mem_free();
    }
#endif  // NC_BLOCK_H