NddArray.hpp

Go to the documentation of this file.

/*
 * This file is part of the DUDS project. It is subject to the BSD-style
 * license terms in the LICENSE file found in the top-level directory of this
 * distribution and at https://github.com/jjackowski/duds/blob/master/LICENSE.
 * No part of DUDS, including this file, may be copied, modified, propagated,
 * or distributed except according to the terms contained in the LICENSE file.
 *
 * Copyright (C) 2017  Jeff Jackowski
 */
#ifndef NDDARRAY_HPP
#define NDDARRAY_HPP

#include <vector>
#include <initializer_list>
#include <duds/general/Errors.hpp>
#include <boost/serialization/split_member.hpp>
#include <boost/serialization/nvp.hpp>
#include <boost/serialization/vector.hpp>

namespace duds { namespace general {

struct NddArrayError : virtual std::exception, virtual boost::exception { };

struct EmptyDimensionError : NddArrayError { };

struct OutOfRangeError : NddArrayError /*, virtual std::out_of_range {
    OutOfRangeError() : std::out_of_range("") { }
}; */  { };

struct DimensionMismatchError : NddArrayError { };

struct ZeroSizeError : DimensionMismatchError { };

template <class T>
class NddArray {
public:
    typedef std::size_t SizeType;
    typedef std::vector<SizeType> DimVec;
    typedef std::initializer_list<SizeType>  DimList;
    typedef T* iterator;
    typedef const T* const_iterator;
private:
    DimVec dsize;
    T *array;
    SizeType elems;
    void makeArray() {
        // work out the total number of elements
        DimVec::const_iterator iter = dsize.begin();
        elems = *(iter++);
        while (iter != dsize.end()) {
            elems *= *(iter++);
        }
        // check for a zero-size dimension
        if (!elems) {
            array = nullptr;
            dsize.clear();
            DUDS_THROW_EXCEPTION(EmptyDimensionError());
        }
        // allocate memory
        array = new T[elems];
    }
    void copyElements(const NddArray &src) {
        // is there something to copy?
        if (elems) {
            // would be nice if constructors could be avoided here and the copy
            // constructor used instead of assignment in the first loop below
            array = new T[elems];
            T *t = array, *ot = src.array;
            try {
                // assign each element
                for (SizeType i = elems; i > 0; --i, ++t, ++ot) {
                    *t = *ot;
                }
            } catch (...) {
                // dismantle what has been built
                clear();
                throw;
            }
        } else {
            // source is empty; array pointer could be anything
            array = nullptr;
        }
    }
    template <class Dim>
    const T &indexArray(const Dim &pos) const {
        // cannot index into an array with zero dimensions
        if (dsize.empty()) {
            DUDS_THROW_EXCEPTION(ZeroSizeError());
        }
        // the position must have as many items as dimensions in the array
        if (pos.size() != dsize.size()) {
            DUDS_THROW_EXCEPTION(DimensionMismatchError());
        }
        typename Dim::const_iterator p = pos.begin();
        DimVec::const_iterator d = dsize.begin();
        SizeType index = 0, step = 1;
        do {
            // range check
            if (*p >= *d) {
                DUDS_THROW_EXCEPTION(OutOfRangeError());
            }
            // advance index
            index += *p * step;
            // compute number of items to skip per unit in the next dimension
            step *= *d;
            // next position & dimension
            ++p;
            ++d;
        } while (d != dsize.end());
        // send back the requested elenent
        return array[index];
    }
public:
    NddArray() : array(nullptr), elems(0) { }
    NddArray(const DimList &dims) : dsize(dims) {
        if (dims.size() > 0) {
            makeArray();
        }
    }
    NddArray(const DimVec &dims) : dsize(dims) {
        if (!dims.empty()) {
            makeArray();
        }
    }
    template <class Dim>
    NddArray(const Dim &dims) : dsize(dims.first(), dims.last()) {
        if (!dsize.empty()) {
            makeArray();
        }
    }
    NddArray(const NddArray &ndda) : elems(ndda.elems), dsize(ndda.dsize) {
        copyElements(ndda);
    }
    NddArray(NddArray &&ndda) noexcept :
    elems(ndda.elems), dsize(std::move(ndda.dsize)) {
        array = ndda.array;
        ndda.array = nullptr;
        ndda.elems = 0;
    }
    ~NddArray() noexcept {
        clear();
    }
    NddArray &operator=(const NddArray &ndda) {
        dsize = ndda.dsize;
        elems = ndda.elems;
        delete [] array;
        copyElements(ndda);
        return *this;
    }
    NddArray &operator=(NddArray &&ndda) noexcept {
        elems = ndda.elems;
        dsize = std::move(ndda.dsize);
        delete [] array;
        array = ndda.array;
        ndda.array = nullptr;
        ndda.elems = 0;
        return *this;
    }
    template <class AV>
    void copyFrom(const AV &av) {
        // size the array to match the array/vector
        remake({av.size()});
        // copy elements
        T *dest = array;
        typename AV::const_iterator src = av.begin();
        for (; src != av.end(); ++src, ++dest) {
            *dest = *src;
        }
    }
    template <std::size_t N>
    void copyFrom(const std::array<T, N> &a) {
        copyFrom< std::array< T, N > >(a);
    }
    void copyFrom(const std::vector<T> &v) {
        copyFrom< std::vector< T > >(v);
    }
    template <std::size_t N>
    void copyFrom(const T (&a)[N]) {
        // size the array to match the array
        remake({N});
        // copy elements
        T *dest = array;
        const T *src = a;
        for (std::size_t loop = N; loop; ++src, ++dest, --loop) {
            *dest = *src;
        }
    }
    template <std::size_t X, std::size_t Y>
    void copyFrom(const T (&a)[X][Y]) {
        // size the array to match the array
        remake({X,Y});
        // copy elements
        T *dest = array;
        std::size_t x, y = 0;
        for (; y < Y; ++y) {
            for (x = 0; x < X; ++dest, ++x) {
                *dest = a[x][y];
            }
        }
    }
    template <std::size_t N>
    NddArray &operator=(const std::array<T, N> &a) {
        copyFrom< std::array< T, N > >(a);
        return *this;
    }
    NddArray &operator=(const std::vector<T> &v) {
        copyFrom< std::vector< T > >(v);
        return *this;
    }
    template <std::size_t N>
    NddArray &operator=(const T (&a)[N]) {
        copyFrom<N>(a);
        return *this;
    }
    template <std::size_t X, std::size_t Y>
    NddArray &operator=(const T (&a)[X][Y]) {
        copyFrom<X,Y>(a);
        return *this;
    }
    template <std::size_t N>
    void copyTo(std::array<T, N> &a) const {
        // must be exactly one dimension
        if (dsize.size() != 1) {
            DUDS_THROW_EXCEPTION(DimensionMismatchError());
        }
        // copy elements
        const T *src = array;
        typename std::array<T, N>::iterator i = a.begin();
        std::size_t loop = std::min(elems, a.size());
        for (; loop; ++i, ++src, --loop) {
            *i = *src;
        }
    }
    void copyTo(std::vector<T> &v) const {
        // must be exactly one dimension
        if (dsize.size() != 1) {
            DUDS_THROW_EXCEPTION(DimensionMismatchError());
        }
        // resize the vector to match
        v.resize(elems);
        // copy elements
        const T *src = array;
        typename std::vector<T>::iterator i = v.begin();
        for (; i != v.end(); ++i, ++src) {
            *i = *src;
        }
    }
    template <std::size_t N>
    void copyTo(T (&a)[N]) const {
        // must be exactly one dimension
        if (dsize.size() != 1) {
            DUDS_THROW_EXCEPTION(DimensionMismatchError());
        }
        // copy elements
        const T *src = array;
        T *dest = a;
        std::size_t loop = std::min(elems, N);
        for (; loop; ++dest, ++src, --loop) {
            *dest = *src;
        }
    }
    template <std::size_t X, std::size_t Y>
    void copyTo(T (&a)[X][Y]) const {
        // must be exactly two dimensions
        if (dsize.size() != 2) {
            DUDS_THROW_EXCEPTION(DimensionMismatchError());
        }
        // copy elements
        const T *src;
        const std::size_t xs = std::min(X, dsize[0]);
        const std::size_t ys = std::min(Y, dsize[1]);
        std::size_t x, y = 0;
        for (; y < ys; ++y) {
            src = &at({0,y});
            for (x = 0; x < xs; ++src, ++x) {
                a[x][y] = *src;
            }
        }
    }
    template <class Dim>
    T &operator()(const Dim &pos) {
        // remove the const specifier from the return value of indexArray()
        // to avoid writing the function twice
        return const_cast<T&>(indexArray(pos));
    }
    T &operator()(const DimList &pos) {
        // remove the const specifier from the return value of indexArray()
        // to avoid writing the function twice
        return const_cast<T&>(indexArray<DimList>(pos));
    }
    template <class Dim>
    const T &operator()(const Dim &pos) const {
        return indexArray(pos);
    }
    const T &operator()(const DimList &pos) const {
        return indexArray<DimList>(pos);
    }
    template <class Dim>
    T &at(const Dim &pos) {
        // remove the const specifier from the return value of indexArray()
        // to avoid writing the function twice
        return const_cast<T&>(indexArray(pos));
    }
    T &at(const DimList &pos) {
        // remove the const specifier from the return value of indexArray()
        // to avoid writing the function twice
        return const_cast<T&>(indexArray<DimList>(pos));
    }
    template <class Dim>
    const T &at(const Dim &pos) const {
        return indexArray(pos);
    }
    const T &at(const DimList &pos) const {
        return indexArray<DimList>(pos);
    }
    T &front() {
        if (!array) {
            DUDS_THROW_EXCEPTION(ZeroSizeError());
        }
        return *array;
    }
    const T &front() const {
        if (!array) {
            DUDS_THROW_EXCEPTION(ZeroSizeError());
        }
        return *array;
    }
    T &back() {
        if (!array) {
            DUDS_THROW_EXCEPTION(ZeroSizeError());
        }
        return array[elems - 1];
    }
    const T &back() const {
        if (!array) {
            DUDS_THROW_EXCEPTION(ZeroSizeError());
        }
        return array[elems - 1];
    }
    T *begin() {
        return array;
    }
    const T *begin() const {
        return array;
    }
    const T *cbegin() const {
        return array;
    }
    T *end() {
        return array + elems;
    }
    const T *end() const {
        return array + elems;
    }
    const T *cend() const {
        return array + elems;
    }
    bool operator==(const NddArray &ndda) const {
        // check dimensions
        if ((elems != ndda.elems) || (dsize != ndda.dsize)) {
            return false;
        }
        // same dimensions; check array elements
        T *t = array, *o = ndda.array;
        for (SizeType i = elems; i; --i, ++t, ++o) {
            if (!(*t == *o)) {
                return false;
            }
        }
        // everything matches
        return true;
    }
    bool operator!=(const NddArray &ndda) const {
        // check dimensions
        if ((elems != ndda.elems) || (dsize != ndda.dsize)) {
            return true;
        }
        // same dimensions; check array elements
        T *t = array, *o = ndda.array;
        for (SizeType i = elems; i; --i, ++t, ++o) {
            if (*t != *o) {
                return true;
            }
        }
        // everything matches
        return false;
    }
    SizeType numdims() const {
        return dsize.size();
    }
    SizeType dim(SizeType n) const {
        if (n >= dsize.size()) {
            DUDS_THROW_EXCEPTION(OutOfRangeError());
        }
        return dsize[n];
    }
    const DimVec &dim() const {
        return dsize;
    }
    SizeType numelems() const {
        return elems;
    }
    bool empty() const {
        return !array;
    }
    void clear() noexcept { // destructors must never throw
        delete [] array;
        array = nullptr;
        dsize.clear();
        elems = 0;
    }
    void remake(const DimList &dims) {
        // no dimensions?
        if (dims.size() == 0) {
            // be empty
            clear();
            return;
        }
        // destroy existing elements
        delete [] array;
        // store new dimensions
        dsize = dims;
        // make stuff
        makeArray();
    }
    void remake(const DimVec &dims) {
        // no dimensions?
        if (dims.empty()) {
            // be empty
            clear();
            return;
        }
        // destroy existing elements
        delete [] array;
        // store new dimensions
        dsize = dims;
        // make stuff
        makeArray();
    }
    template <class Dim>
    NddArray makeWithNewSize(const Dim &dims) const {
        // no dimensions in new size?
        if (dims.size() == 0) {
            // empty
            return NddArray();
        }
        // no dimensions in current size?
        if (!array) {
            // make array of given size
            return NddArray(dims);
        }
        // new array for the new size
        NddArray na(dims);  // may throw EmptyDimensionError
        // union of source & destination dimensions
        DimVec uniondim(std::min(dsize.size(), dims.size()));
        typename Dim::const_iterator diter = dims.begin();
        SizeType idx = 0;  // dimension index
        do {
            // Find the length covered by old & new size. The result will be
            // greater than zero. If any length was zero, the construction of na
            // above threw an exception, so no need to check here.
            uniondim[idx] = (std::min(dsize[idx], *diter));
            ++diter;
        } while (++idx < uniondim.size());
        idx = 0;
        // position vectors for source & destination
        DimVec spos(numdims(), 0), dpos(na.numdims());
        // pointers to inside the arrays
        const T *sitm = array;  // source
        T *ditm = na.array;     // destination
        // loop to copy
        do {
            // copy element; first element can always be copied
            *ditm = *sitm;
            // loop to advance position
            do {
                // next position
                spos[idx] += 1;
                // check range on this dimension
                if (spos[idx] >= uniondim[idx]) {
                    // went beyond; go back to start of this dimension
                    spos[idx] = 0;
                } else {
                    // in bounds; use this position
                    break;
                }
            } while (++idx < uniondim.size());
            // modified 1st dimension only?
            if (!idx) {
                // The next element is the next in the 1D storage array. Advance
                // the pointers to quickly get to the next element.
                ++sitm;
                ++ditm;
            // modified more than one dimension in the position?
            } else if (idx < uniondim.size()) {
                // next time, start position advance at 1st dimension
                idx = 0;
                // new source address
                sitm = &at(spos);
                // set new destination position
                dpos = spos;
                dpos.resize(na.numdims());
                // new destination address
                ditm = &na.at(dpos);
            // modified all dimensions to zero?
            } else {
                // all done
                break;
            }
        } while (true);
        // return the new array
        return na;
    }
    NddArray makeWithNewSize(const DimList &dims) const {
        return makeWithNewSize<DimList>(dims);
    }
    template <class Dim>
    void resize(const Dim &dims) {
        *this = std::move(makeWithNewSize(dims));
    }
    void resize(const DimList &dims) {
        *this = std::move(makeWithNewSize<DimList>(dims));
    }
    SizeType size() const {
        return elems;
    }
    void swap(NddArray &other) {
        dsize.swap(other.dsize);
        std::swap(array, other.array);
        std::swap(elems, other.elems);
    };
private:
    // serialization support
    friend class boost::serialization::access;
    BOOST_SERIALIZATION_SPLIT_MEMBER();
    template <class A>
    void save(A &a, const unsigned int) const {
        // store the dimensions
        a & BOOST_SERIALIZATION_NVP(dsize);
        // store more only if not empty
        if (!dsize.empty()) {
            // write out elements
            const T *t = array;
            for (SizeType i = elems; i > 0; --i, ++t) {
                a & boost::serialization::make_nvp("item", *t);
            }
        }
    }
    template <class A>
    void load(A &a, const unsigned int) {
        // destroy existing contents
        if (array) {
            clear();
        }
        // recover the dimensions
        a & BOOST_SERIALIZATION_NVP(dsize);
        // there is only more if the array isn't empty
        if (!dsize.empty()) {
            try {
                // allocate space
                makeArray();
                // read in elements
                T *t = array;
                for (SizeType i = elems; i > 0; --i, ++t) {
                    a & boost::serialization::make_nvp("item", *t);
                }
            } catch (...) {
                // not sure if this is needed
                clear();
                throw;
            }
        }
    }
};

template <class T>
void swap(NddArray<T> &one, NddArray<T> &two) {
    one.swap(two);
}

} }

#endif        //  #ifndef NDDARRAY_HPP