algorithm to find all adjacent vertices on the Hexagonal Lattice

adjacent_hex.cpp

#include <cinttypes>
#include <iostream>
#include <iterator>
#include <utility>

/*
  Find all adjacent vertices in the Hex Board.

    position = position - 1 + difference;

  List of all position differences to get adjacent nodes:

   row col
    -1  0  00 01
    -1 +1  00 10
     0 -1  01 00
     0 +1  01 10
    +1 -1  10 00
    +1  0  10 01

    end (sentinel value): -1  1111 1111 1111 1111

  I am using bit strings to store all this differences.

  To get current diff value, just use `diff &= 3`, and `diff >>= 2` to
  get the next diff.

  6*2=12 bits is enough to store them

    0 - middle/center
    1 - top/left
    2 - bottom/right

   BitString for different positions:

    middle-center:
      r: 1111 101001010000
      c: 1111 010010001001
    middle-left:
      r: 11111111 10010000
      c: 11111111 01101001
    middle-right:
      r: 11111111 10100100
      c: 11111111 01000001
    top-center:
      r: 11111111 10100101
      c: 11111111 01001000
    top-left:
      r: 111111111111 1001
      c: 111111111111 0110
    top-right:
      r: 1111111111 101001
      c: 1111111111 010000
    bottom-center:
      r: 11111111 01010000
      c: 11111111 10001001
    bottom-left:
      r: 1111111111 010000
      c: 1111111111 101001
    bottom-right:
      r: 111111111111 0100
      c: 111111111111 0001

  I am prepending 1111, so that right arithmetic shift should produce
  larger values and in the end we are getting (-1 as a sentinel value)
*/

static const uint32_t _Diffs[3][3] = {
  {0xf489fa50, 0xff69ff90, 0xff41ffa4},
  {0xff48ffa5, 0xfff6fff9, 0xffd0ffe9},
  {0xff89ff50, 0xffe9ffd0, 0xfff1fff4}
};

struct HexAdjacentIteratorEndTag {};

class HexAdjacentIterator
    : public std::iterator<std::forward_iterator_tag, std::pair<int16_t, int16_t>> {
public:
  HexAdjacentIterator(int16_t row, int16_t col)
      : _row(row), _col(col),
  _diff(_Diffs[0][0]) {}

  HexAdjacentIterator(int16_t row, int16_t col, int16_t size)
      : _row(row),
        _col(col),
  _diff(_Diffs[!row + ((row == (size - 1)) << 1)][!col + ((col == (size - 1)) << 1)]) {}

  HexAdjacentIterator(int16_t row, int16_t col, HexAdjacentIteratorEndTag)
      : _row(row), _col(col), _diff(-1) {}

  HexAdjacentIterator(int16_t row, int16_t col, int16_t rd, int16_t cd)
      : _row(row), _col(col), _row_diff(rd), _col_diff(cd) {}

  HexAdjacentIterator& operator++() noexcept {
    _row_diff >>= 2;
    _col_diff >>= 2;
    return *this;
  }

  std::pair<int16_t, int16_t> operator*() noexcept {
    int16_t row = _row - 1 + (_row_diff & 3);
    int16_t col = _col - 1 + (_col_diff & 3);
    return std::make_pair(row, col);
  }

  bool operator<(const HexAdjacentIterator &o) const noexcept {
    return _row_diff < o._row_diff;
  }

  bool operator!=(const HexAdjacentIterator &o) const noexcept {
    return _row_diff != o._row_diff;
  }

private:
  int16_t _row;
  int16_t _col;
  union {
    struct {
      int16_t _row_diff;
      int16_t _col_diff;
    };
    uint32_t _diff;
  };
};

class HexAdjacentRangeBase {
public:
  HexAdjacentRangeBase(int16_t row, int16_t col)
      : _row(row), _col(col) {}

  HexAdjacentIterator end() noexcept {
    return HexAdjacentIterator(_row, _col, HexAdjacentIteratorEndTag());
  }

protected:
  int16_t _row;
  int16_t _col;
};

template<bool Bounded>
class HexAdjacentRange : public HexAdjacentRangeBase {
public:
  HexAdjacentRange(int16_t row, int16_t col)
      : HexAdjacentRangeBase(row, col) {}

  HexAdjacentIterator begin() noexcept {
    return HexAdjacentIterator(_row, _col);
  }
};

template<>
class HexAdjacentRange<true> : public HexAdjacentRangeBase {
public:
  HexAdjacentRange(int16_t row, int16_t col, int16_t size)
      : HexAdjacentRangeBase(row, col), _size(size) {}

  HexAdjacentIterator begin() noexcept {
    return HexAdjacentIterator(_row, _col, _size);
  }

private:
  int16_t _size;
};


inline HexAdjacentRange<false> makeHexAdjacentRange(int16_t row, int16_t col) {
  return HexAdjacentRange<false>(row, col);
}
inline HexAdjacentRange<true> makeHexAdjacentRange(int16_t row, int16_t col,
                                                   int16_t size) {
  return HexAdjacentRange<true>(row, col, size);
}

int main(int argc, char* argv[]) {
  int a, b;
  std::cin >> a >> b;

  for (auto i: makeHexAdjacentRange(a, b, 3)) {
    std::cout << std::get<0>(i) << ':' << std::get<1>(i) << std::endl;
  }
  std::cout << std::endl;
}