Copyright	2021 Eric Mertens
License	ISC
Maintainer	emertens@gmail.com
Safe Haskell	Safe-Inferred
Language	Haskell2010

Advent.Box

Description

This module expresses boxes as a list of bounds on each axis. This representation enables efficient intersection and subtraction operations.

Synopsis

type Box' (n :: Natural) = Box (FromNatural n)
data Box (a :: Nat) where
- Pt :: Box 'Z
- Dim :: forall (n :: Nat). !Int -> !Int -> Box n -> Box ('S n)
size :: forall (n :: Nat). Box n -> Int
intersectBox :: forall (n :: Nat). Box n -> Box n -> Maybe (Box n)
intersectBoxes :: forall (n :: Nat). HasCallStack => [Box n] -> Maybe (Box n)
subtractBox :: forall (n :: Nat). Box n -> Box n -> [Box n]
subtractBox' :: forall (n :: Nat). Box n -> Box n -> [Box n]
coverBox :: forall (n :: Nat). Box n -> Box n -> Box n
coverBoxes :: forall (n :: Nat). HasCallStack => [Box n] -> Box n
unionBoxes :: forall (a :: Nat). [Box a] -> [Box a]

Documentation

type Box' (n :: Natural) = Box (FromNatural n) Source #

Type synonym for Box allowing the use of natural number literals.

data Box (a :: Nat) where Source #

An n-dimensional box.

Constructors

Pt
Fields :: Box 'Z A single point
Dim
Fields :: forall (n :: Nat). !Int inclusive lower bound -> !Int exclusive upper bound -> Box n lower dimensional box -> Box ('S n) A box extended along an axis

Instances

Instances details

UnfoldNat n => Read (Box n) Source #
Instance details Defined in Advent.Box Methods readsPrec :: Int -> ReadS (Box n) # readList :: ReadS [Box n] # readPrec :: ReadPrec (Box n) # readListPrec :: ReadPrec [Box n] #
Show (Box n) Source #
Instance details Defined in Advent.Box Methods showsPrec :: Int -> Box n -> ShowS # show :: Box n -> String # showList :: [Box n] -> ShowS #
Eq (Box n) Source #
Instance details Defined in Advent.Box Methods (==) :: Box n -> Box n -> Bool # (/=) :: Box n -> Box n -> Bool #
Ord (Box n) Source #
Instance details Defined in Advent.Box Methods compare :: Box n -> Box n -> Ordering # (<) :: Box n -> Box n -> Bool # (<=) :: Box n -> Box n -> Bool # (>) :: Box n -> Box n -> Bool # (>=) :: Box n -> Box n -> Bool # max :: Box n -> Box n -> Box n # min :: Box n -> Box n -> Box n #

size :: forall (n :: Nat). Box n -> Int Source #

Returns the number of points contained in a box.

>>> size Pt -- 0D point
1

>>> size (Dim 1 4 Pt) -- 1D segment; length
3

>>> size (Dim 1 4 (Dim 0 3 Pt)) -- 2D rectangle; area
9

>>> size (Dim 1 4 (Dim 0 3 (Dim 0 2 Pt))) -- 3D cuboid; volume
18

intersectBox :: forall (n :: Nat). Box n -> Box n -> Maybe (Box n) Source #

The intersection of two boxes is the intersection of their segments.

>>> intersectBox (Dim 0 2 (Dim 0 3 Pt)) (Dim 1 4 (Dim 2 4 Pt))
Just (Dim 1 2 (Dim 2 3 Pt))

intersectBoxes :: forall (n :: Nat). HasCallStack => [Box n] -> Maybe (Box n) Source #

Intersection of one or more boxes.

subtractBox Source #

Arguments

:: forall (n :: Nat). Box n	remove this
-> Box n	from this
-> [Box n]	leaving these

Subtract the first box from the second box returning a list of boxes that cover all the remaining area.

>>> subtractBox (Dim 2 3 Pt) (Dim 0 4 Pt)
[Dim 0 2 Pt,Dim 3 4 Pt]

>>> subtractBox (Dim 3 5 Pt) (Dim 0 4 Pt)
[Dim 0 3 Pt]

>>> subtractBox (Dim 0 1 Pt) (Dim 1 2 Pt)
[Dim 1 2 Pt]

>>> subtractBox (Dim 0 1 (Dim 0 1 Pt)) (Dim 0 2 (Dim 0 2 Pt))
[Dim 1 2 (Dim 0 2 Pt),Dim 0 1 (Dim 1 2 Pt)]

>>> subtractBox (Dim 0 9 Pt) (Dim 3 6 Pt)
[]

subtractBox' :: forall (n :: Nat). Box n -> Box n -> [Box n] Source #

Worker for subtractBox where the first argument is a subset of the second argument.

coverBox :: forall (n :: Nat). Box n -> Box n -> Box n Source #

Compute the box that encompasses both arguments. This might cover extra elements as no such box might exist that is the perfect union of the two boxes.

>>> coverBox (Dim 2 3 Pt) (Dim 0 4 Pt)
Dim 0 4 Pt

>>> coverBox (Dim 1 3 Pt) (Dim 2 4 Pt)
Dim 1 4 Pt

>>> coverBox (Dim 0 1 Pt) (Dim 3 4 Pt)
Dim 0 4 Pt

coverBoxes :: forall (n :: Nat). HasCallStack => [Box n] -> Box n Source #

Compute the box that encompasses all of the boxes in the list.

unionBoxes :: forall (a :: Nat). [Box a] -> [Box a] Source #

Given a list of potentially overlapping boxes create a new list of boxes that cover the same region but which do not overlap.

Note that this function does not attempt to combine boxes.

>>> unionBoxes [Dim 2 3 Pt, Dim 0 4 Pt]
[Dim 2 3 Pt,Dim 0 2 Pt,Dim 3 4 Pt]

>>> unionBoxes [Dim 1 3 Pt, Dim 2 4 Pt]
[Dim 1 3 Pt,Dim 3 4 Pt]

>>> unionBoxes [Dim 0 1 Pt, Dim 3 4 Pt]
[Dim 0 1 Pt,Dim 3 4 Pt]