Range.h

/*
 * Gamedev Framework (gf)
 * Copyright (C) 2016-2019 Julien Bernard
 *
 * This software is provided 'as-is', without any express or implied
 * warranty.  In no event will the authors be held liable for any damages
 * arising from the use of this software.
 *
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute it
 * freely, subject to the following restrictions:
 *
 * 1. The origin of this software must not be misrepresented; you must not
 *    claim that you wrote the original software. If you use this software
 *    in a product, an acknowledgment in the product documentation would be
 *    appreciated but is not required.
 * 2. Altered source versions must be plainly marked as such, and must not be
 *    misrepresented as being the original software.
 * 3. This notice may not be removed or altered from any source distribution.
 */
#ifndef GF_RANGE_H
#define GF_RANGE_H

#include <cstddef>
#include <iterator>

#include "Math.h"
#include "Vector.h"

namespace gf {
#ifndef DOXYGEN_SHOULD_SKIP_THIS
inline namespace v1 {
#endif

  template<typename T>
  struct Range {
    T lo; 
    T hi; 

    struct Iterator {
      using difference_type = std::ptrdiff_t;
      using value_type = T;
      using pointer = value_type;
      using reference = value_type;
      using iterator_category = std::bidirectional_iterator_tag;

      T index; 

      constexpr Iterator(T iteratorIndex) noexcept
      : index(iteratorIndex)
      {
      }

      void swap(Iterator& other) noexcept {
        using std::swap;
        swap(index, other.index);
      }

      reference operator*() noexcept {
        return index;
      }

      pointer operator->() noexcept {
        return index;
      }

      Iterator& operator++() noexcept {
        ++index;
        return *this;
      }

      Iterator operator++(int) noexcept {
        Iterator copy = *this;
        ++index;
        return copy;
      }

      Iterator& operator--() noexcept {
        --index;
        return *this;
      }

      Iterator operator--(int) noexcept {
        Iterator copy = *this;
        --index;
        return copy;
      }

      constexpr bool operator!=(const Iterator& other) const noexcept {
        return index != other.index;
      }

      constexpr bool operator==(const Iterator& other) const noexcept {
        return index == other.index;
      }
    };

    constexpr bool contains(T value) const noexcept {
      return lo <= value && value < hi;
    }

    constexpr Iterator begin() const noexcept {
      return Iterator(lo);
    }

    constexpr Iterator end() const noexcept {
      return Iterator(hi);
    }

    constexpr T length() const noexcept {
      return hi - lo;
    }

    constexpr bool isEmpty() const noexcept {
      return lo >= hi;
    }

    constexpr bool isValid() const noexcept {
      return lo <= hi;
    }
  };

  template<typename T>
  inline
  void swap(typename Range<T>::Iterator& lhs, typename Range<T>::Iterator& rhs) noexcept {
    lhs.swap(rhs);
  }

  using RangeF = Range<float>;

  using RangeI = Range<int>;

  using RangeU = Range<unsigned>;

  using RangeZ = Range<std::size_t>;

// MSVC does not like extern template
#ifndef _MSC_VER
  extern template struct Range<float>;
  extern template struct Range<int>;
  extern template struct Range<unsigned>;
#endif



  template<typename T>
  struct PositionRange {
    Range<T> first;   
    Range<T> second;  

    struct Iterator {
      using difference_type = std::ptrdiff_t;
      using value_type = Vector<T, 2>;
      using pointer = value_type;
      using reference = value_type;
      using iterator_category = std::forward_iterator_tag;

      Range<T> range;
      Vector<T, 2> position;

      constexpr Iterator(Range<T> iteratorRange, Vector<T, 2> iteratorPosition) noexcept
      : range(iteratorRange)
      , position(iteratorPosition)
      {
      }

      void swap(Iterator& other) noexcept {
        using std::swap;
        swap(range, other.range);
        swap(position, other.position);
      }

      reference operator*() noexcept {
        return position;
      }

      pointer operator->() noexcept {
        return position;
      }

      Iterator& operator++() noexcept {
        step();
        return *this;
      }

      Iterator operator++(int) noexcept {
        Iterator copy = *this;
        step();
        return copy;
      }

      constexpr bool operator!=(const Iterator& other) const noexcept {
        return position.x != other.position.x || position.y != other.position.y;
      }

      constexpr bool operator==(const Iterator& other) const noexcept {
        return position.x == other.position.x && position.y == other.position.y;
      }

    private:
      void step() noexcept {
        ++position.x;

        if (position.x >= range.hi) {
          position.x = range.lo;
          ++position.y;
        }
      }
    };

    constexpr Iterator begin() const noexcept {
      return Iterator(first, { first.lo, second.lo });
    }

    constexpr Iterator end() const noexcept {
      return Iterator(first, { first.lo, second.hi });
    }
  };

  template<typename T>
  inline
  void swap(typename PositionRange<T>::Iterator& lhs, typename PositionRange<T>::Iterator& rhs) noexcept {
    lhs.swap(rhs);
  }


  template<typename T>
  struct NeighborSquareRange {
    Range<T> first;   
    Range<T> second;  
    Vector<T, 2> origin;

    struct Iterator {
      using difference_type = std::ptrdiff_t;
      using value_type = Vector<T, 2>;
      using pointer = value_type;
      using reference = value_type;
      using iterator_category = std::forward_iterator_tag;

      Vector<T, 2> position;
      const NeighborSquareRange<T> *parent;

      constexpr Iterator(Vector<T, 2> iteratorPosition, const NeighborSquareRange<T> *iteratorParent) noexcept
      : position(iteratorPosition)
      , parent(iteratorParent)
      {
        if (isNotNeighbor(position)) {
          step();
        }
      }

      constexpr Iterator(Vector<T, 2> iteratorPosition) noexcept
      : position(iteratorPosition)
      , parent(nullptr)
      {
      }

      void swap(Iterator& other) noexcept {
        using std::swap;
        swap(position, other.position);
        swap(parent, other.parent);
      }

      reference operator*() noexcept {
        return position;
      }

      pointer operator->() noexcept {
        return position;
      }

      Iterator& operator++() noexcept {
        step();
        return *this;
      }

      Iterator operator++(int) noexcept {
        Iterator copy = *this;
        step();
        return copy;
      }

      constexpr bool operator!=(const Iterator& other) const noexcept {
        return position.x != other.position.x || position.y != other.position.y;
      }

      constexpr bool operator==(const Iterator& other) const noexcept {
        return position.x == other.position.x && position.y == other.position.y;
      }

    private:
      void step() noexcept {
        do {
          ++position.x;

          if (position.x >= parent->first.hi) {
            position.x = parent->first.lo;
            ++position.y;
          }
        } while (isNotNeighbor(position));
      }

      bool isNotNeighbor(Vector<T, 2> other) const noexcept {
        return other.x == parent->origin.x && other.y == parent->origin.y;
      }
    };

    constexpr Iterator begin() const noexcept {
      return Iterator({ first.lo, second.lo }, this);
    }

    constexpr Iterator end() const noexcept {
      return Iterator({ first.lo, second.hi });
    }
  };

  template<typename T>
  inline
  void swap(typename NeighborSquareRange<T>::Iterator& lhs, typename NeighborSquareRange<T>::Iterator& rhs) noexcept {
    lhs.swap(rhs);
  }


  template<typename T>
  struct NeighborDiamondRange {
    Range<T> first;   
    Range<T> second;  
    Vector<T, 2> origin;
    T radius;

    struct Iterator {
      using difference_type = std::ptrdiff_t;
      using value_type = Vector<T, 2>;
      using pointer = value_type;
      using reference = value_type;
      using iterator_category = std::forward_iterator_tag;

      Vector<T, 2> position;
      const NeighborDiamondRange<T> *parent;

      constexpr Iterator(Vector<T, 2> iteratorPosition, const NeighborDiamondRange<T> *iteratorParent) noexcept
      : position(iteratorPosition)
      , parent(iteratorParent)
      {
        if (isNotNeighbor(position)) {
          step();
        }
      }

      constexpr Iterator(Vector<T, 2> iteratorPosition) noexcept
      : position(iteratorPosition)
      , parent(nullptr)
      {
      }

      void swap(Iterator& other) noexcept {
        using std::swap;
        swap(position, other.position);
        swap(parent, other.parent);
      }

      reference operator*() noexcept {
        return position;
      }

      pointer operator->() noexcept {
        return position;
      }

      Iterator& operator++() noexcept {
        step();
        return *this;
      }

      Iterator operator++(int) noexcept {
        Iterator copy = *this;
        step();
        return copy;
      }

      constexpr bool operator!=(const Iterator& other) const noexcept {
        return position.x != other.position.x || position.y != other.position.y;
      }

      constexpr bool operator==(const Iterator& other) const noexcept {
        return position.x == other.position.x && position.y == other.position.y;
      }

    private:
      void step() noexcept {
        do {
          ++position.x;

          if (position.x >= parent->first.hi) {
            position.x = parent->first.lo;
            ++position.y;

            if (position.y >= parent->second.hi) {
              break;
            }
          }
        } while (isNotNeighbor(position));
      }

      bool isNotNeighbor(Vector<T, 2> other) const noexcept {
        return isOrigin(other) || isOutOfDiamond(position);
      }

      bool isOrigin(Vector<T, 2> other) const noexcept {
        return other.x == parent->origin.x && other.y == parent->origin.y;
      }

      bool isOutOfDiamond(Vector<T, 2> other) const noexcept {
        return gf::absdiff(other.x, parent->origin.x) + gf::absdiff(other.y, parent->origin.y) > parent->radius;
      }
    };

    constexpr Iterator begin() const noexcept {
      return Iterator({ first.lo, second.lo }, this);
    }

    constexpr Iterator end() const noexcept {
      return Iterator({ first.lo, second.hi });
    }
  };

  template<typename T>
  inline
  void swap(typename NeighborDiamondRange<T>::Iterator& lhs, typename NeighborDiamondRange<T>::Iterator& rhs) noexcept {
    lhs.swap(rhs);
  }


#ifndef DOXYGEN_SHOULD_SKIP_THIS
}
#endif
}

#endif // GF_RANGE_H