Hexagonal Layout

Coordinate system that represents a hexagonal grid of compile-time coordinate types. In contrast to Cartesian layouts, the faces of hexagonal layouts can be arranged in different ways. The most obvious are the distinction between the orientation of the hexagons that can either be pointy-top up or flat-top up.

C+Python

Header: fiction/layouts/hexagonal_layout.hpp

struct pointy_top_hex

   / \
 /     \
|       |
|       |
 \     /
   \ /

Subclassed by fiction::even_row_hex, fiction::odd_row_hex

struct flat_top_hex

   _____
  /     \
 /       \
 \       /
  \_____/

Subclassed by fiction::even_column_hex, fiction::odd_column_hex

Furthermore, when assuming rectangular-ish layouts, either odd or even rows or columns can be shifted inwards, yielding a total of four different orientations.

struct odd_row_hex : public fiction::pointy_top_hex

       / \     / \     / \
     /     \ /     \ /     \
    | (0,0) | (1,0) | (2,0) |
    |       |       |       |
     \     / \     / \     / \
       \ /     \ /     \ /     \
        | (0,1) | (1,1) | (2,1) |
        |       |       |       |
       / \     / \     / \     /
     /     \ /     \ /     \ /
    | (0,2) | (1,2) | (2,2) |
    |       |       |       |
     \     / \     / \     /
       \ /     \ /     \ /

struct even_row_hex : public fiction::pointy_top_hex

       / \     / \     / \
     /     \ /     \ /     \
    | (0,0) | (1,0) | (2,0) |
    |       |       |       |
   / \     / \     / \     /
 /     \ /     \ /     \ /
| (0,1) | (1,1) | (2,1) |
|       |       |       |
 \     / \     / \     / \
   \ /     \ /     \ /     \
    | (0,2) | (1,2) | (2,2) |
    |       |       |       |
     \     / \     / \     /
       \ /     \ /     \ /

struct odd_column_hex : public fiction::flat_top_hex

   _____         _____
  /     \       /     \
 / (0,0) \_____/ (2,0) \_____
 \       /     \       /     \
  \_____/ (1,0) \_____/ (3,0) \
  /     \       /     \       /
 / (0,1) \_____/ (2,1) \_____/
 \       /     \       /     \
  \_____/ (1,1) \_____/ (3,1) \
  /     \       /     \       /
 / (0,2) \_____/ (2,2) \_____/
 \       /     \       /
  \_____/       \_____/

struct even_column_hex : public fiction::flat_top_hex

          _____         _____
         /     \       /     \
   _____/ (1,0) \_____/ (3,0) \
  /     \       /     \       /
 / (0,0) \_____/ (2,0) \_____/
 \       /     \       /     \
  \_____/ (1,1) \_____/ (3,1) \
  /     \       /     \       /
 / (0,1) \_____/ (2,1) \_____/
 \       /     \       /     \
  \_____/ (1,2) \_____/ (3,2) \
        \       /     \       /
         \_____/       \_____/

The hexagonal layout supports all of them via template parameters.

template<typename OffsetCoordinateType = offset::ucoord_t, typename HexagonalCoordinateSystem = even_row_hex, typename CubeCoordinateType = cube::coord_t>
class hexagonal_layout

A layout type that utilizes offset coordinates to represent a hexagonal grid. Its faces are organized in an offset coordinate system as provided. Hexagons can be in the pointy_top_hex or flat_top_hex orientation. Based on that, two respectively possible coordinate systems emerge accordingly: odd_row_hex and even_row_hex for pointy tops and odd_column_hex and even_column_hex for flat tops. All are sketched in ASCII above.

Other representations would be using cube or axial coordinates for instance, but since we want the layouts to be rectangular-ish, offset coordinates make the most sense here.

https://www.redblobgames.com/grids/hexagons/ is a wonderful resource on the topic.

Template Parameters:

• OffsetCoordinateType – The coordinate implementation to be used. Offset coordinates are required.

• HexagonalCoordinateSystem – One of the following: odd_row_hex, even_row_hex, odd_column_hex, even_column_hex.

• CubeCoordinateType – Internally, cube coordinates are needed for certain algorithms or calculations.

Public Functions

inline explicit hexagonal_layout(const aspect_ratio &ar = {})

Standard constructor. The given aspect ratio points to the highest possible coordinate in the layout. That means in the even_column_hex ASCII layout representation above ar = (3,2). Consequently, with ar = (0,0), the layout has exactly one coordinate.

Parameters:

ar – Highest possible position in the layout.

inline hexagonal_layout clone() const noexcept

Clones the layout returning a deep copy.

Returns:

Deep copy of the layout.

template<typename X, typename Y, typename Z = uint64_t>
inline constexpr OffsetCoordinateType coord(const X x, const Y y, const Z z = 0ul) const noexcept

Creates and returns a coordinate in the layout from the given x-, y-, and z-values.

Note

This function is equivalent to calling OffsetCoordinateType(x, y, z).

Template Parameters:

• X – x-type.

• Y – y-type.

• Z – z-type.

Parameters:

• x – x-value.

• y – y-value.

• z – z-value.

Returns:

A coordinate in the layout of type OffsetCoordinateType.

inline uint64_t x() const noexcept

Returns the layout’s x-dimension, i.e., returns the biggest x-value that still belongs to the layout.

Returns:

x-dimension.

inline uint64_t y() const noexcept

Returns the layout’s y-dimension, i.e., returns the biggest y-value that still belongs to the layout.

Returns:

y-dimension.

inline uint64_t z() const noexcept

Returns the layout’s z-dimension, i.e., returns the biggest z-value that still belongs to the layout.

Returns:

z-dimension.

inline uint64_t area() const noexcept

Returns the layout’s number of faces depending on the coordinate type.

Returns:

Area of layout.

inline void resize(const aspect_ratio &ar) noexcept

Updates the layout’s dimensions, effectively resizing it.

Parameters:

ar – New aspect ratio.

inline bool is_in_odd_row(const OffsetCoordinateType &c) const noexcept

Checks if the given coordinate is located in a row with an odd index.

Parameters:

c – Coordinate to check.

Returns:

true iff c is located in an odd row.

inline bool is_in_even_row(const OffsetCoordinateType &c) const noexcept

Checks if the given coordinate is located in a row with an even index.

Parameters:

c – Coordinate to check.

Returns:

true iff c is located in an even row.

inline bool is_in_odd_column(const OffsetCoordinateType &c) const noexcept

Checks if the given coordinate is located in a column with an odd index.

Parameters:

c – Coordinate to check.

Returns:

true iff c is located in an odd column.

inline bool is_in_even_column(const OffsetCoordinateType &c) const noexcept

Checks if the given coordinate is located in a column with an even index.

Parameters:

c – Coordinate to check.

Returns:

true iff c is located in an even column.

inline constexpr OffsetCoordinateType north(const OffsetCoordinateType &c) const noexcept

Returns the coordinate that is directly adjacent in northern direction of a given coordinate c, i.e., the face whose y-dimension is lower by 1. If c’s y-dimension is already at minimum, c is returned instead.

Parameters:

c – Coordinate whose northern counterpart is desired.

Returns:

Coordinate adjacent and north of c.

inline constexpr OffsetCoordinateType north_east(const OffsetCoordinateType &c) const noexcept

Returns the coordinate that is located in north-eastern direction of a given coordinate c. Depending on the hexagonal orientation of the layout, the dimension values of the returned coordinate may differ.

Parameters:

c – Coordinate whose north-eastern counterpart is desired.

Returns:

Coordinate directly north-eastern of c.

inline OffsetCoordinateType east(const OffsetCoordinateType &c) const noexcept

Returns the coordinate that is directly adjacent in eastern direction of a given coordinate c, i.e., the face whose x-dimension is higher by 1. If c’s x-dimension is already at maximum, c is returned instead.

Parameters:

c – Coordinate whose eastern counterpart is desired.

Returns:

Coordinate adjacent and east of c.

inline constexpr OffsetCoordinateType south_east(const OffsetCoordinateType &c) const noexcept

Returns the coordinate that is located in south-eastern direction of a given coordinate c. Depending on the hexagonal orientation of the layout, the dimension values of the returned coordinate may differ.

Parameters:

c – Coordinate whose south-eastern counterpart is desired.

Returns:

Coordinate directly south-eastern of c.

inline OffsetCoordinateType south(const OffsetCoordinateType &c) const noexcept

Returns the coordinate that is directly adjacent in southern direction of a given coordinate c, i.e., the face whose y-dimension is higher by 1. If c’s y-dimension is already at maximum, c is returned instead.

Parameters:

c – Coordinate whose southern counterpart is desired.

Returns:

Coordinate adjacent and south of c.

inline constexpr OffsetCoordinateType south_west(const OffsetCoordinateType &c) const noexcept

Returns the coordinate that is located in south-western direction of a given coordinate c. Depending on the hexagonal orientation of the layout, the dimension values of the returned coordinate may differ.

Parameters:

c – Coordinate whose south-western counterpart is desired.

Returns:

Coordinate directly south-western of c.

inline constexpr OffsetCoordinateType west(const OffsetCoordinateType &c) const noexcept

Returns the coordinate that is directly adjacent in western direction of a given coordinate c, i.e., the face whose x-dimension is lower by 1. If c’s x-dimension is already at minimum, c is returned instead.

Parameters:

c – Coordinate whose western counterpart is desired.

Returns:

Coordinate adjacent and west of c.

inline constexpr OffsetCoordinateType north_west(const OffsetCoordinateType &c) const noexcept

Returns the coordinate that is located in north-western direction of a given coordinate c. Depending on the hexagonal orientation of the layout, the dimension values of the returned coordinate may differ.

Parameters:

c – Coordinate whose north-western counterpart is desired.

Returns:

Coordinate directly north-western of c.

inline OffsetCoordinateType above(const OffsetCoordinateType &c) const noexcept

Returns the coordinate that is directly above a given coordinate c, i.e., the face whose z-dimension is higher by 1. If c’s z-dimension is already at maximum, c is returned instead.

Parameters:

c – Coordinate whose above counterpart is desired.

Returns:

Coordinate directly above c.

inline constexpr OffsetCoordinateType below(const OffsetCoordinateType &c) const noexcept

Returns the coordinate that is directly below a given coordinate c, i.e., the face whose z-dimension is lower by 1. If c’s z-dimension is already at minimum, c is returned instead.

Parameters:

c – Coordinate whose below counterpart is desired.

Returns:

Coordinate directly below c.

inline constexpr bool is_north_of(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Returns true iff coordinate c2 is directly north of coordinate c1.

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is directly north of c1.

inline bool is_east_of(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Returns true iff coordinate c2 is directly east of coordinate c1.

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is directly east of c1.

inline bool is_south_of(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Returns true iff coordinate c2 is directly south of coordinate c1.

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is directly south of c1.

inline constexpr bool is_west_of(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Returns true iff coordinate c2 is directly west of coordinate c1.

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is directly west of c1.

inline bool is_adjacent_of(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Returns true iff coordinate c2 is either north, north-east, east, south-east, south, south-west, west, or north-west of coordinate c1.

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is directly adjacent to c1 in one of the six different ordinal directions possible for the layout’s hexagonal orientation.

inline bool is_adjacent_elevation_of(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Similar to is_adjacent_of but also considers c1’s elevation, i.e., if c2 is adjacent to above(c1) or below(c1).

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is either adjacent of c1 or c1’s elevations.

inline bool is_above(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Returns true iff coordinate c2 is directly above coordinate c1.

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is directly above c1.

inline constexpr bool is_below(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Returns true iff coordinate c2 is directly below coordinate c1.

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is directly below c1.

inline constexpr bool is_northwards_of(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Returns true iff coordinate c2 is somewhere north of coordinate c1.

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is somewhere north of c1.

inline constexpr bool is_eastwards_of(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Returns true iff coordinate c2 is somewhere east of coordinate c1.

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is somewhere east of c1.

inline constexpr bool is_southwards_of(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Returns true iff coordinate c2 is somewhere south of coordinate c1.

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is somewhere south of c1.

inline constexpr bool is_westwards_of(const OffsetCoordinateType &c1, const OffsetCoordinateType &c2) const noexcept

Returns true iff coordinate c2 is somewhere west of coordinate c1.

Parameters:

• c1 – Base coordinate.

• c2 – Coordinate to test for its location in relation to c1.

Returns:

true iff c2 is somewhere west of c1.

inline constexpr bool is_at_northern_border(const OffsetCoordinateType &c) const noexcept

Returns whether the given coordinate is located at the layout’s northern border where y is minimal.

Parameters:

c – Coordinate to check for border location.

Returns:

true iff c is located at the layout’s northern border.

inline bool is_at_eastern_border(const OffsetCoordinateType &c) const noexcept

Returns whether the given coordinate is located at the layout’s eastern border where x is maximal.

Parameters:

c – Coordinate to check for border location.

Returns:

true iff c is located at the layout’s northern border.

inline bool is_at_southern_border(const OffsetCoordinateType &c) const noexcept

Returns whether the given coordinate is located at the layout’s southern border where y is maximal.

Parameters:

c – Coordinate to check for border location.

Returns:

true iff c is located at the layout’s southern border.

inline constexpr bool is_at_western_border(const OffsetCoordinateType &c) const noexcept

Returns whether the given coordinate is located at the layout’s western border where x is minimal.

Parameters:

c – Coordinate to check for border location.

Returns:

true iff c is located at the layout’s western border.

inline bool is_at_any_border(const OffsetCoordinateType &c) const noexcept

Returns whether the given coordinate is located at any of the layout’s borders where x or y are either minimal or maximal.

Parameters:

c – Coordinate to check for border location.

Returns:

true iff c is located at any of the layout’s borders.

inline OffsetCoordinateType northern_border_of(const OffsetCoordinateType &c) const noexcept

Returns the coordinate with the same x and z values as a given coordinate but that is located at the layout’s northern border.

Parameters:

c – Coordinate whose border counterpart is desired.

Returns:

The northern border equivalent of c.

inline OffsetCoordinateType eastern_border_of(const OffsetCoordinateType &c) const noexcept

Returns the coordinate with the same y and z values as a given coordinate but that is located at the layout’s eastern border.

Parameters:

c – Coordinate whose border counterpart is desired.

Returns:

The eastern border equivalent of c.

inline OffsetCoordinateType southern_border_of(const OffsetCoordinateType &c) const noexcept

Returns the coordinate with the same x and z values as a given coordinate but that is located at the layout’s southern border.

Parameters:

c – Coordinate whose border counterpart is desired.

Returns:

The southern border equivalent of c.

inline OffsetCoordinateType western_border_of(const OffsetCoordinateType &c) const noexcept

Returns the coordinate with the same y and z values as a given coordinate but that is located at the layout’s western border.

Parameters:

c – Coordinate whose border counterpart is desired.

Returns:

The western border equivalent of c.

inline constexpr bool is_ground_layer(const OffsetCoordinateType &c) const noexcept

Returns whether the given coordinate is located in the ground layer where z is minimal.

Parameters:

c – Coordinate to check for elevation.

Returns:

true iff c is in ground layer.

inline constexpr bool is_crossing_layer(const OffsetCoordinateType &c) const noexcept

Returns whether the given coordinate is located in a crossing layer where z is not minimal.

Parameters:

c – Coordinate to check for elevation.

Returns:

true iff c is in a crossing layer.

inline constexpr bool is_within_bounds(const OffsetCoordinateType &c) const noexcept

Returns whether the given coordinate is located within the layout bounds.

Parameters:

c – Coordinate to check for boundary.

Returns:

true iff c is located within the layout bounds.

inline auto coordinates(const OffsetCoordinateType &start = {}, const OffsetCoordinateType &stop = {}) const

Returns a range of all coordinates accessible in the layout between start and stop. If no values are provided, all coordinates in the layout will be included. The returned iterator range points to the first and last coordinate, respectively. The range object can be used within a for-each loop. Incrementing the iterator is equivalent to nested for loops in the order z, y, x. Consequently, the iteration will happen inside out, i.e., x will be iterated first, then y, then z.

Parameters:

• start – First coordinate to include in the range of all coordinates.

• stop – Last coordinate (exclusive) to include in the range of all coordinates.

Returns:

An iterator range from start to stop. If they are not provided, the first/last coordinate is used as a default.

template<typename Fn>
inline void foreach_coordinate(Fn &&fn, const OffsetCoordinateType &start = {}, const OffsetCoordinateType &stop = {}) const

Applies a function to all coordinates accessible in the layout between start and stop. The iteration order is the same as for the coordinates function.

Template Parameters:

Fn – Functor type that has to comply with the restrictions imposed by mockturtle::foreach_element.

Parameters:

• fn – Functor to apply to each coordinate in the range.

• start – First coordinate to include in the range of all coordinates.

• stop – Last coordinate (exclusive) to include in the range of all coordinates.

inline auto ground_coordinates(const OffsetCoordinateType &start = {}, const OffsetCoordinateType &stop = {}) const

Returns a range of all coordinates accessible in the layout’s ground layer between start and stop. The iteration order is the same as for the coordinates function but without the z dimension.

Parameters:

• start – First coordinate to include in the range of all ground coordinates.

• stop – Last coordinate (exclusive) to include in the range of all ground coordinates.

Returns:

An iterator range from start to stop. If they are not provided, the first/last coordinate in the ground layer is used as a default.

template<typename Fn>
inline void foreach_ground_coordinate(Fn &&fn, const OffsetCoordinateType &start = {}, const OffsetCoordinateType &stop = {}) const

Applies a function to all coordinates accessible in the layout’s ground layer between start and stop. The iteration order is the same as for the ground_coordinates function.

Template Parameters:

Fn – Functor type that has to comply with the restrictions imposed by mockturtle::foreach_element.

Parameters:

• fn – Functor to apply to each coordinate in the range.

• start – First coordinate to include in the range of all ground coordinates.

• stop – Last coordinate (exclusive) to include in the range of all ground coordinates.

inline auto adjacent_coordinates(const OffsetCoordinateType &c) const noexcept

Returns a container that contains all coordinates that are adjacent to a given one. Thereby, cardinal and ordinal directions are being considered, i.e., the container will contain all coordinates ac for which is_adjacent(c, ac) returns true.

Coordinates that are outside of the layout bounds are not considered. Thereby, the size of the returned container is at most 6.

Parameters:

c – Coordinate whose adjacent ones are desired.

Returns:

A container that contains all of c’s adjacent coordinates.

template<typename Fn>
inline void foreach_adjacent_coordinate(const OffsetCoordinateType &c, Fn &&fn) const

Applies a function to all coordinates adjacent to a given one in accordance with adjacent_coordinates. Thereby, cardinal and ordinal directions are being considered, i.e., the given function is applied to all coordinates ac for which is_adjacent(c, ac) returns true.

Coordinates that are outside of the layout bounds are not considered. Thereby, at most 6 coordinates are touched.

Template Parameters:

Fn – Functor type.

Parameters:

• c – Coordinate whose adjacent ones are desired.

• fn – Functor to apply to each of c’s adjacent coordinates.

inline auto adjacent_opposite_coordinates(const OffsetCoordinateType &c) const noexcept

Returns a container that contains all coordinates pairs of opposing adjacent coordinates with respect to a given one. In this hexagonal layout, the container content depends on the hexagonal orientation.

In case of a pointy_top_hex orientation, the container will contain (east(c), west(c)), (north_east(c), south_west(c)), (north_west(c), south_east(c)). In case of a flat_top_hex orientation, the container will contain (north(c), south(c)), (north_east(c), south_west(c)), (north_west(c), south_east(c)) instead.

This function comes in handy when straight lines on the layout are to be examined.

Coordinates outside of the layout bounds are not being considered.

Parameters:

c – Coordinate whose opposite ones are desired.

Returns:

A container that contains pairs of c’s opposing coordinates.

template<typename Fn>
inline void foreach_adjacent_opposite_coordinates(const OffsetCoordinateType &c, Fn &&fn) const

Applies a function to all opposing coordinate pairs adjacent to a given one. In this hexagonal layout, the function application depends on the hexagonal orientation.

In case of a pointy_top_hex orientation, the function will apply to (east(c), west(c)), (north_east(c), south_west(c)), (north_west(c), south_east(c)). In case of a flat_top_hex orientation, the function will apply to (north(c), south(c)), (north_east(c), south_west(c)), (north_west(c), south_east(c)) instead.

This function comes in handy when straight lines on the layout are to be examined.

Coordinates outside of the layout bounds are not being considered.

Template Parameters:

Fn – Functor type.

Parameters:

• c – Coordinate whose opposite adjacent ones are desired.

• fn – Functor to apply to each of c’s opposite adjacent coordinate pairs.

inline constexpr CubeCoordinateType to_cube_coordinate(const OffsetCoordinateType &offset_coord) const noexcept

Converts an offset coordinate to a cube coordinate.

This implementation is adapted from https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cpp

Parameters:

offset_coord – Offset coordinate to convert.

Returns:

Cube coordinate representing offset_coord in the layout’s hexagonal orientation.

inline constexpr OffsetCoordinateType to_offset_coordinate(const CubeCoordinateType &cube_coord) const noexcept

Converts a cube coordinate to an offset coordinate.

This implementation is adapted from https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cpp

Parameters:

cube_coord – Cube coordinate to convert.

Returns:

Offset coordinate representing cube_coord in the layout’s hexagonal orientation.

struct hexagonal_layout_storage