This module defines the tree structure used in the Bounds
type. You don't need to import this module if you are just doing collision detection. But you may find it useful for debugging.
We identify nodes in the tree using a two-dimensional coordinate system. The first coordinate measures distance from the root node. The second coordinate measures how far "from the left" the node is. So the root node is at (0,0), its two children are (1,0) and (1,1), their children are (2,0) through (2,3), and so on.
A binary tree type. The the internal nodes can store differently-typed data than the leaf nodes.
Return the maximum depth of the tree.
depth (Leaf 1) == 1
depth (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5)) == 3
Return a list of leaf values, tagged with tree coordinates.
leaves (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5))
== [ ((2,0), 3), ((2,1), 4), ((1,1), 5) ]
Return of list of internal node values, tagged with tree coordinates.
internals (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5))
== [ ((0,0), 1), ((1,0), 2) ]
Return the subtree of a given tree, whose root node is at the given coordinates. If the coordinates are out of bounds, return the nearest ancestor.
subtreeAt (1,0) (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5))
== Node 2 (Leaf 3) (Leaf 4)
subtreeAt (2,1) (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5))
== Leaf 4
subtreeAt (2,3) (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5))
== Leaf 5
Given a pair of tree coordinates, return the coordinates of the left child node.
toTheLeft (0,0) == (1,0)
toTheLeft (1,1) == (2,2)
toTheLeft (4,7) == (5,14)
Given a pair of tree coordinates, return the coordinates of the right child node.
toTheRight (0,0) == (1,1)
toTheRight (1,1) == (2,3)
toTheRight (4,7) == (5,15)
module Collision.Tree exposing (Tree(..), leaves, internals, depth, subtreeAt, toTheLeft, toTheRight)
{-| This module defines the tree structure used in the `Bounds` type. You don't need to import this module if you are just doing collision detection. But you may find it useful for debugging.
We identify nodes in the tree using a two-dimensional coordinate system. The first coordinate measures distance from the root node. The second coordinate measures how far "from the left" the node is. So the root node is at (0,0), its two children are (1,0) and (1,1), their children are (2,0) through (2,3), and so on.
# Definition
@docs Tree
# Inspecting
@docs depth, leaves, internals, subtreeAt, toTheLeft, toTheRight
-}
{-| A binary tree type. The the internal nodes can store differently-typed data than the leaf nodes.
-}
type Tree a b
= Leaf b
| Node a (Tree a b) (Tree a b)
{-| Return the maximum depth of the tree.
depth (Leaf 1) == 1
depth (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5)) == 3
-}
depth : Tree a b -> Int
depth tree =
case tree of
Leaf _ ->
1
Node _ left right ->
1 + max (depth left) (depth right)
{-| Return a list of leaf values, tagged with tree coordinates.
leaves (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5))
== [ ((2,0), 3), ((2,1), 4), ((1,1), 5) ]
-}
leaves : Tree a b -> List ( ( Int, Int ), b )
leaves tree =
leavesRecurse ( 0, 0 ) tree
leavesRecurse : ( Int, Int ) -> Tree a b -> List ( ( Int, Int ), b )
leavesRecurse coords tree =
case tree of
Leaf a ->
[ ( coords, a ) ]
Node _ left right ->
leavesRecurse (toTheLeft coords) left
++ leavesRecurse (toTheRight coords) right
{-| Return of list of internal node values, tagged with tree coordinates.
internals (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5))
== [ ((0,0), 1), ((1,0), 2) ]
-}
internals : Tree a b -> List ( ( Int, Int ), a )
internals tree =
internalsRecurse ( 0, 0 ) tree
internalsRecurse : ( Int, Int ) -> Tree a b -> List ( ( Int, Int ), a )
internalsRecurse coords tree =
case tree of
Leaf _ ->
[]
Node a left right ->
( coords, a )
:: internalsRecurse (toTheLeft coords) left
++ internalsRecurse (toTheRight coords) right
{-| Given a pair of tree coordinates, return the coordinates of the left child node.
toTheLeft (0,0) == (1,0)
toTheLeft (1,1) == (2,2)
toTheLeft (4,7) == (5,14)
-}
toTheLeft : ( Int, Int ) -> ( Int, Int )
toTheLeft ( level, offset ) =
( level + 1, 2 * offset )
{-| Given a pair of tree coordinates, return the coordinates of the right child node.
toTheRight (0,0) == (1,1)
toTheRight (1,1) == (2,3)
toTheRight (4,7) == (5,15)
-}
toTheRight : ( Int, Int ) -> ( Int, Int )
toTheRight ( level, offset ) =
( level + 1, 2 * offset + 1 )
{-| Return the subtree of a given tree, whose root node is at the given coordinates. If the coordinates are out of bounds, return the nearest ancestor.
subtreeAt (1,0) (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5))
== Node 2 (Leaf 3) (Leaf 4)
subtreeAt (2,1) (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5))
== Leaf 4
subtreeAt (2,3) (Node 1 (Node 2 (Leaf 3) (Leaf 4)) (Leaf 5))
== Leaf 5
-}
subtreeAt : ( Int, Int ) -> Tree a b -> Tree a b
subtreeAt ( level, offset ) tree =
case tree of
Leaf b ->
tree
Node a left right ->
if level == 0 then
tree
else
let
midpoint =
2 ^ (level - 1)
in
if offset < midpoint then
subtreeAt ( level - 1, offset ) left
else
subtreeAt ( level - 1, offset - midpoint ) right