PackedIndex.h

Go to the documentation of this file.

// -*- LSST-C++ -*-
/*
 * Developed for the LSST Data Management System.
 * This product includes software developed by the LSST Project
 * (https://www.lsst.org).
 * See the COPYRIGHT file at the top-level directory of this distribution
 * for details of code ownership.
 *
 * 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.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
#ifndef LSST_AFW_MATH_POLYNOMIALS_PackedIndex_h_INCLUDED
#define LSST_AFW_MATH_POLYNOMIALS_PackedIndex_h_INCLUDED

namespace lsst { namespace geom { namespace polynomials {

enum class PackingOrder {

    YX,

    XY
};

struct Index2d {

    constexpr Index2d() noexcept : flat(0), nx(0), ny(0) {}

    constexpr Index2d(std::size_t flat_, std::size_t nx_, std::size_t ny_) noexcept :
        flat(flat_), nx(nx_), ny(ny_)
    {}

    constexpr bool operator==(Index2d const & other) const noexcept {
        return flat == other.flat && nx == other.nx && ny == other.ny;
    }

    constexpr bool operator!=(Index2d const & other) const noexcept {
        return !(*this == other);
    }

    std::size_t flat; 
    std::size_t nx;    
    std::size_t ny;    
};

namespace detail {

// Specialization of all PackedIndexIterator/PackedIndexRange logic
// that isn't common across PackingOrders.
template <PackingOrder packing> struct PackingOrderTraits;

template <>
struct PackingOrderTraits<PackingOrder::YX> {

    // Return the offset of the given coefficient after the (nx + ny) offset is subtracted off.
    static std::size_t computeInnerIndex(std::size_t nx, std::size_t ny) { return nx; }

    static void increment(Index2d & index) {
        if (index.ny == 0) {
            index.ny = index.nx + 1;
            index.nx = 0;
        } else {
            --index.ny;
            ++index.nx;
        }
    }

    // Return the nx and ny values appropriate for the end iterator of a range of the given order.
    static std::size_t getEndX(std::size_t order) { return 0; }
    static std::size_t getEndY(std::size_t order) { return order + 1; }

};

template <>
struct PackingOrderTraits<PackingOrder::XY> {

    // Return the offset of the given coefficient after the (nx + ny) offset is subtracted off.
    static std::size_t computeInnerIndex(std::size_t nx, std::size_t ny) { return ny; }

    static void increment(Index2d & index) {
        if (index.nx == 0) {
            index.nx = index.ny + 1;
            index.ny = 0;
        } else {
            --index.nx;
            ++index.ny;
        }
    }

    // Return the nx and ny values appropriate for the end iterator of a range of the given order.
    static std::size_t getEndX(std::size_t order) { return order + 1; }
    static std::size_t getEndY(std::size_t order) { return 0; }

};

} // namespace detail

template <PackingOrder packing>
class PackedIndexIterator {
    using Traits = detail::PackingOrderTraits<packing>;
public:

    using difference_type = std::ptrdiff_t;
    using value_type = Index2d;
    using pointer = Index2d const *;
    using reference = Index2d const &;
    using iterator_category = std::input_iterator_tag;

    static constexpr std::size_t computeOffset(std::size_t order) noexcept {
        return order*(order + 1)/2;
    }

    static constexpr std::size_t computeSize(std::size_t order) noexcept {
        return computeOffset(order + 1);
    }

    static constexpr std::size_t computeIndex(std::size_t nx, std::size_t ny) noexcept {
        return computeOffset(nx + ny) + Traits::computeInnerIndex(nx, ny);
    }

    static constexpr PackedIndexIterator makeEnd(std::size_t order) noexcept {
        return PackedIndexIterator(order);
    }

    constexpr PackedIndexIterator() noexcept : _index() {}

    constexpr PackedIndexIterator(std::size_t nx, std::size_t ny) noexcept :
        _index(computeIndex(nx, ny), nx, ny)
    {}

    constexpr reference operator*() const noexcept { return _index; }

    constexpr pointer operator->() const noexcept { return &_index; }

    PackedIndexIterator & operator++() noexcept {
        ++_index.flat;
        Traits::increment(_index);
        return *this;
    }

    PackedIndexIterator operator++(int) noexcept {
        PackedIndexIterator r(*this);
        ++(*this);
        return r;
    }

    constexpr bool operator==(PackedIndexIterator const & other) const noexcept {
        return _index == other._index;
    }

    constexpr bool operator!=(PackedIndexIterator const & other) const noexcept {
        return !(*this == other);
    }

private:

    constexpr PackedIndexIterator(std::size_t order) noexcept :
        _index(computeOffset(order + 1), Traits::getEndX(order), Traits::getEndY(order))
    {}

    Index2d _index;
};

template <PackingOrder packing>
class PackedIndexRange {
public:

    using iterator = PackedIndexIterator<packing>;
    using const_iterator = iterator;
    using value_type = typename iterator::value_type;
    using reference = typename iterator::reference;
    using pointer = typename iterator::pointer;
    using difference_type = typename iterator::difference_type;
    using size_type = std::size_t;

    static constexpr std::size_t computeOffset(std::size_t order) noexcept {
        return iterator::computeOffset(order);
    }

    static constexpr std::size_t computeSize(std::size_t order) noexcept {
        return iterator::computeSize(order);
    }

    static constexpr std::size_t computeIndex(std::size_t nx, std::size_t ny) noexcept {
        return iterator::computeIndex(nx, ny);
    }

    constexpr PackedIndexRange(iterator first, iterator last) noexcept :
        _begin(first),
        _end(last)
    {}

    constexpr iterator begin() const noexcept { return _begin; }

    constexpr iterator cbegin() const noexcept { return _begin; }

    constexpr iterator end() const noexcept { return _end; }

    constexpr iterator cend() const noexcept { return _end; }

    constexpr std::size_t size() const noexcept { return _end->flat - _begin->flat; }

    constexpr bool empty() const noexcept { return size() == 0u; }

    constexpr bool operator==(PackedIndexRange const & other) const noexcept {
        return _begin == other._begin && _end == other._end;
    }

    constexpr bool operator!=(PackedIndexRange const & other) const noexcept {
        return !(*this == other);
    }

private:
    iterator _begin;
    iterator _end;
};

}}} // namespace lsst::geom::polynomials

#endif // !LSST_AFW_MATH_POLYNOMIALS_PackedIndex_h_INCLUDED