-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Tools for working with regular grids (graphs, lattices). -- -- Provides tools for working with regular arrangements of tiles, such as -- might be used in a board game or some other type of grid map. -- Currently supports triangular, square, and hexagonal tiles, with -- various 2D and toroidal layouts. NOTE: Version 3.0 changed the order -- of parameters for many functions. This makes it easier for the user to -- write mapping and folding operations. @package grid @version 3.0 -- | A module containing private Grid internals. Most developers -- should use Grid instead. This module is subject to change -- without notice. module Math.Geometry.GridInternal -- | A regular arrangement of tiles. Minimal complete definition: -- indices, distance and size. class Eq x => Grid g s x | g -> s, g -> x where minDistance g xs x = minimum . map (distance g x) $ xs neighbours g x = filter (\ a -> distance g x a ≡ 1) $ indices g numNeighbours g = length . neighbours g contains g x = x `elem` indices g viewpoint g p = map f (indices g) where f x = (x, distance g p x) tileCount = length . indices empty g = tileCount g ≡ 0 nonEmpty = not . empty edges g = nubBy sameEdge $ concatMap (`adjacentEdges` g) $ indices g isAdjacent g a b = distance g a b ≡ 1 adjacentTilesToward g a b | a ≡ b = [] | otherwise = filter f $ neighbours g a where f x = distance g x b ≡ distance g a b - 1 minimalPaths g a b | a ≡ b = [[a]] | distance g a b ≡ 1 = [[a, b]] | otherwise = map (a :) xs where xs = concatMap (\ x -> minimalPaths g x b) ys ys = adjacentTilesToward g a b indices :: Grid g s x => g -> [x] distance :: Grid g s x => g -> x -> x -> Int minDistance :: Grid g s x => g -> [x] -> x -> Int size :: Grid g s x => g -> s neighbours :: Grid g s x => g -> x -> [x] numNeighbours :: Grid g s x => g -> x -> Int contains :: Grid g s x => g -> x -> Bool viewpoint :: Grid g s x => g -> x -> [(x, Int)] tileCount :: Grid g s x => g -> Int empty :: Grid g s x => g -> Bool nonEmpty :: Grid g s x => g -> Bool edges :: Grid g s x => g -> [(x, x)] isAdjacent :: (Grid g s x, Grid g s x) => g -> x -> x -> Bool adjacentTilesToward :: Grid g s x => g -> x -> x -> [x] minimalPaths :: Grid g s x => g -> x -> x -> [[x]] -- | A regular arrangement of tiles with an edge. Minimal complete -- definition: boundary. class Grid g s x => BoundedGrid g s x where isBoundary g x = x `elem` boundary g centre g = map fst . head . reverse . groupBy ((==) `on` snd) . sortBy (comparing snd) $ xds where xds = map (\ y -> (y, minDistance g bs y)) $ indices g bs = boundary g isCentre g x = x `elem` centre g boundary :: BoundedGrid g s x => g -> [x] isBoundary :: BoundedGrid g s x => g -> x -> Bool centre :: BoundedGrid g s x => g -> [x] isCentre :: BoundedGrid g s x => g -> x -> Bool -- | A triangular grid with triangular tiles. The grid and its indexing -- scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data TriTriGrid -- | triTriGrid s returns a triangular grid with sides of -- length s, using triangular tiles. If s is -- nonnegative, the resulting grid will have s^2 tiles. -- Otherwise, the resulting grid will be empty and the list of indices -- will be null. triTriGrid :: Int -> TriTriGrid -- | A Parallelogrammatical grid with triangular tiles. The grid and its -- indexing scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data ParaTriGrid -- | paraTriGrid r c returns a grid in the shape of a -- parallelogram with r rows and c columns, using -- triangular tiles. If r and c are both nonnegative, -- the resulting grid will have 2*r*c tiles. Otherwise, the -- resulting grid will be empty and the list of indices will be null. paraTriGrid :: Int -> Int -> ParaTriGrid -- | A rectangular grid with square tiles. The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data RectSquareGrid -- | rectSquareGrid r c produces a rectangular grid with -- r rows and c columns, using square tiles. If -- r and c are both nonnegative, the resulting grid -- will have r*c tiles. Otherwise, the resulting grid will be -- empty and the list of indices will be null. rectSquareGrid :: Int -> Int -> RectSquareGrid -- | A toroidal grid with square tiles. The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data TorSquareGrid -- | torSquareGrid r c returns a toroidal grid with -- r rows and c columns, using square tiles. If -- r and c are both nonnegative, the resulting grid -- will have r*c tiles. Otherwise, the resulting grid will be -- empty and the list of indices will be null. torSquareGrid :: Int -> Int -> TorSquareGrid -- | A hexagonal grid with hexagonal tiles The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data HexHexGrid -- | hexHexGrid s returns a grid of hexagonal shape, with -- sides of length s, using hexagonal tiles. If s is -- nonnegative, the resulting grid will have 3*s*(s-1) + 1 -- tiles. Otherwise, the resulting grid will be empty and the list of -- indices will be null. hexHexGrid :: Int -> HexHexGrid -- | A parallelogramatical grid with hexagonal tiles The grid and its -- indexing scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data ParaHexGrid -- | paraHexGrid r c returns a grid in the shape of a -- parallelogram with r rows and c columns, using -- hexagonal tiles. If r and c are both nonnegative, -- the resulting grid will have r*c tiles. Otherwise, the -- resulting grid will be empty and the list of indices will be null. paraHexGrid :: Int -> Int -> ParaHexGrid instance Eq TriTriGrid instance Eq ParaTriGrid instance Eq RectSquareGrid instance Eq TorSquareGrid instance Eq HexHexGrid instance Eq ParaHexGrid instance BoundedGrid ParaHexGrid (Int, Int) (Int, Int) instance Grid ParaHexGrid (Int, Int) (Int, Int) instance Show ParaHexGrid instance BoundedGrid HexHexGrid Int (Int, Int) instance Grid HexHexGrid Int (Int, Int) instance Show HexHexGrid instance Grid TorSquareGrid (Int, Int) (Int, Int) instance Show TorSquareGrid instance BoundedGrid RectSquareGrid (Int, Int) (Int, Int) instance Grid RectSquareGrid (Int, Int) (Int, Int) instance Show RectSquareGrid instance BoundedGrid ParaTriGrid (Int, Int) (Int, Int) instance Grid ParaTriGrid (Int, Int) (Int, Int) instance Show ParaTriGrid instance BoundedGrid TriTriGrid Int (Int, Int) instance Grid TriTriGrid Int (Int, Int) instance Show TriTriGrid -- | A regular arrangement of tiles. Grids have a variety of uses, -- including games and self-organising maps. -- -- NOTE: Version 3.0 changed the order of parameters for many functions. -- This makes it easier for the user to write mapping and folding -- operations. module Math.Geometry.Grid -- | A regular arrangement of tiles. Minimal complete definition: -- indices, distance and size. class Eq x => Grid g s x | g -> s, g -> x where minDistance g xs x = minimum . map (distance g x) $ xs neighbours g x = filter (\ a -> distance g x a ≡ 1) $ indices g numNeighbours g = length . neighbours g contains g x = x `elem` indices g viewpoint g p = map f (indices g) where f x = (x, distance g p x) tileCount = length . indices empty g = tileCount g ≡ 0 nonEmpty = not . empty edges g = nubBy sameEdge $ concatMap (`adjacentEdges` g) $ indices g isAdjacent g a b = distance g a b ≡ 1 adjacentTilesToward g a b | a ≡ b = [] | otherwise = filter f $ neighbours g a where f x = distance g x b ≡ distance g a b - 1 minimalPaths g a b | a ≡ b = [[a]] | distance g a b ≡ 1 = [[a, b]] | otherwise = map (a :) xs where xs = concatMap (\ x -> minimalPaths g x b) ys ys = adjacentTilesToward g a b indices :: Grid g s x => g -> [x] distance :: Grid g s x => g -> x -> x -> Int minDistance :: Grid g s x => g -> [x] -> x -> Int size :: Grid g s x => g -> s neighbours :: Grid g s x => g -> x -> [x] numNeighbours :: Grid g s x => g -> x -> Int contains :: Grid g s x => g -> x -> Bool viewpoint :: Grid g s x => g -> x -> [(x, Int)] tileCount :: Grid g s x => g -> Int empty :: Grid g s x => g -> Bool nonEmpty :: Grid g s x => g -> Bool edges :: Grid g s x => g -> [(x, x)] isAdjacent :: (Grid g s x, Grid g s x) => g -> x -> x -> Bool adjacentTilesToward :: Grid g s x => g -> x -> x -> [x] minimalPaths :: Grid g s x => g -> x -> x -> [[x]] -- | A regular arrangement of tiles with an edge. Minimal complete -- definition: boundary. class Grid g s x => BoundedGrid g s x where isBoundary g x = x `elem` boundary g centre g = map fst . head . reverse . groupBy ((==) `on` snd) . sortBy (comparing snd) $ xds where xds = map (\ y -> (y, minDistance g bs y)) $ indices g bs = boundary g isCentre g x = x `elem` centre g boundary :: BoundedGrid g s x => g -> [x] isBoundary :: BoundedGrid g s x => g -> x -> Bool centre :: BoundedGrid g s x => g -> [x] isCentre :: BoundedGrid g s x => g -> x -> Bool -- | A triangular grid with triangular tiles. The grid and its indexing -- scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data TriTriGrid -- | triTriGrid s returns a triangular grid with sides of -- length s, using triangular tiles. If s is -- nonnegative, the resulting grid will have s^2 tiles. -- Otherwise, the resulting grid will be empty and the list of indices -- will be null. triTriGrid :: Int -> TriTriGrid -- | A Parallelogrammatical grid with triangular tiles. The grid and its -- indexing scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data ParaTriGrid -- | paraTriGrid r c returns a grid in the shape of a -- parallelogram with r rows and c columns, using -- triangular tiles. If r and c are both nonnegative, -- the resulting grid will have 2*r*c tiles. Otherwise, the -- resulting grid will be empty and the list of indices will be null. paraTriGrid :: Int -> Int -> ParaTriGrid -- | A rectangular grid with square tiles. The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data RectSquareGrid -- | rectSquareGrid r c produces a rectangular grid with -- r rows and c columns, using square tiles. If -- r and c are both nonnegative, the resulting grid -- will have r*c tiles. Otherwise, the resulting grid will be -- empty and the list of indices will be null. rectSquareGrid :: Int -> Int -> RectSquareGrid -- | A toroidal grid with square tiles. The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data TorSquareGrid -- | torSquareGrid r c returns a toroidal grid with -- r rows and c columns, using square tiles. If -- r and c are both nonnegative, the resulting grid -- will have r*c tiles. Otherwise, the resulting grid will be -- empty and the list of indices will be null. torSquareGrid :: Int -> Int -> TorSquareGrid -- | A hexagonal grid with hexagonal tiles The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data HexHexGrid -- | hexHexGrid s returns a grid of hexagonal shape, with -- sides of length s, using hexagonal tiles. If s is -- nonnegative, the resulting grid will have 3*s*(s-1) + 1 -- tiles. Otherwise, the resulting grid will be empty and the list of -- indices will be null. hexHexGrid :: Int -> HexHexGrid -- | A parallelogramatical grid with hexagonal tiles The grid and its -- indexing scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data ParaHexGrid -- | paraHexGrid r c returns a grid in the shape of a -- parallelogram with r rows and c columns, using -- hexagonal tiles. If r and c are both nonnegative, -- the resulting grid will have r*c tiles. Otherwise, the -- resulting grid will be empty and the list of indices will be null. paraHexGrid :: Int -> Int -> ParaHexGrid -- | Ordered maps from tiles on a grid to values. This module is a wrapper -- around Grid and Map, in order to -- combine the functionality of grids and maps into a single type. module Math.Geometry.GridMap -- | A Map from tile positions in a grid to values. data GridMap g k v -- | Construct a grid map which is strict in the keys (tile positions), but -- lazy in the values. lazyGridMap :: (Ord k, Grid g s k) => g -> [v] -> GridMap g k v -- | Returns the indices of all tiles in a grid. indices :: Grid g s x => g -> [x] -- | distance g a b returns the minimum number of moves -- required to get from the tile at index a to the tile at index -- b in grid g, moving between adjacent tiles at each -- step. (Two tiles are adjacent if they share an edge.) If a or -- b are not contained within g, the result is -- undefined. distance :: Grid g s x => g -> x -> x -> Int -- | Returns the dimensions of the grid. For example, if g is a -- 4x3 rectangular grid, size g would return (4, -- 3), while tileCount g would return 12. size :: Grid g s x => g -> s -- | neighbours g x returns the indices of the tiles in the -- grid g which are adjacent to the tile with index x. neighbours :: Grid g s x => g -> x -> [x] -- | g `'contains'` x returns True if the index -- x is contained within the grid g, otherwise it -- returns false. contains :: Grid g s x => g -> x -> Bool -- | viewpoint g x returns a list of pairs associating the -- index of each tile in g with its distance to the tile with -- index x. If x is not contained within g, -- the result is undefined. viewpoint :: Grid g s x => g -> x -> [(x, Int)] -- | Returns the number of tiles in a grid. Compare with -- size. tileCount :: Grid g s x => g -> Int -- | Returns True if the number of tiles in a grid is zero, -- False otherwise. empty :: Grid g s x => g -> Bool -- | Returns False if the number of tiles in a grid is zero, -- True otherwise. nonEmpty :: Grid g s x => g -> Bool -- | O(min(n,W)). Find the value at a tile position in the grid. -- Calls error when the element can not be found. (!) :: Ord k => GridMap g k v -> k -> v -- | O(min(n,W)). Lookup the value at a tile position in the grid -- map. lookup :: Ord k => k -> GridMap g k v -> Maybe v -- | O(min(n,W)). The expression (findWithDefault def k -- map) returns the value at tile position k or returns -- def when the tile is not within the bounds of the grid map. findWithDefault :: Ord k => v -> k -> GridMap g k v -> v -- | O(min(n,W)). Adjust a value at a specific tile position. When -- the tile is not within the bounds of the grid map, the original grid -- map is returned. adjust :: Ord k => (v -> v) -> k -> GridMap g k v -> GridMap g k v -- | O(min(n,W)). Adjust a value at a specific key. When the tile is -- not within the bounds of the grid map, the original grid map is -- returned. adjustWithKey :: Ord k => (k -> v -> v) -> k -> GridMap g k v -> GridMap g k v -- | O(n). Map a function over all values in the grid map. map :: (a -> b) -> GridMap g k a -> GridMap g k b -- | O(n). Map a function over all values in the grid map. mapWithKey :: (k -> a -> b) -> GridMap g k a -> GridMap g k b -- | O(n). The function mapAccum threads an -- accumulating argument through the grid map. WARNING: The order in -- which the elements are processed is not guaranteed. mapAccum :: (a -> b -> (a, c)) -> a -> GridMap g k b -> (a, GridMap g k c) -- | O(n). The function mapAccumWithKey threads an -- accumulating argument through the grid map. WARNING: The order in -- which the elements are processed is not guaranteed. mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> GridMap g k b -> (a, GridMap g k c) -- | O(n). Fold the values in the grid map using the given -- left-associative binary operator. WARNING: The order in which the -- elements are processed is not guaranteed. fold :: (a -> b -> a) -> a -> GridMap g k b -> a -- | O(n). Fold the keys and values in the grid map using the given -- left-associative binary operator. WARNING: The order in which the -- elements are processed is not guaranteed. foldWithKey :: (a -> k -> b -> a) -> a -> GridMap g k b -> a -- | O(n). A strict version of fold. fold' :: (a -> b -> a) -> a -> GridMap g k b -> a -- | O(n). A strict version of foldWithKey. foldWithKey' :: (a -> k -> b -> a) -> a -> GridMap g k b -> a -- | O(n). Return all elements of the grid map. The order is not -- guaranteed. elems :: GridMap g k a -> [a] -- | O(n*min(n,W)). The set of all tile positions in the grid map. keysSet :: GridMap g k a -> Set k -- | O(n). Returns all key (tile position)/value pairs in the grid -- map. toList :: GridMap g k a -> [(k, a)] instance (Eq g, Eq k, Eq v) => Eq (GridMap g k v) instance (Eq k, Grid g s k) => Grid (GridMap g k v) s k instance (Show g, Show v) => Show (GridMap g k v)