Wumpus.Tree.Design

A variant of the tree drawing algorithm from Andrew Kennedy - Functional Pearls Drawing Trees 1996.

Acknowledgment - although based on Andrew Kennedy's algorithm, this version uses absolute extents rather than relative ones and is a somewhat different in detail if not in spirit to the original.

Any mistakes are mine of course.

Design a tree

data UW

Tree unit width.

Trees are designed with 1.0 as the ideal width between nodes. This is represented as a specific newtype so it can be contextually scaled after the design, before the tree is drawn.

Instances

Eq UW

Floating UW

Fractional UW

Num UW

Ord UW

Real UW

RealFloat UW

RealFrac UW

Show UW

InterpretUnit UW

type CoordTree a = Tree (Point2 UW, a)

Tree annotated with positions.

This is the result of design.

design :: Tree a -> CoordTree a

Design a tree, properly balancing the child nodes oriented at root.

As the design has no y-positions (but by recursion they can be counted) and x-positions are respective to the unit distance 1.0 separating nodes it is rescaled as a post-processing step into drawable coordinates.

Post transform a tree design

scaleTree :: (DrawingCtxM m, InterpretUnit u) => u -> u -> CoordTree a -> m (Tree (Point2 u, a))

scaleTree : sibling_distance * level_distance * CoordTree -> Tree

Scale a CoordTree - this forms a tree where the node label is a pair of Point2 u and an a (usually a LocImage).

orientateTree :: (Real u, Floating u) => TreeDirection -> Tree (Point2 u, a) -> Tree (Point2 u, a)

Orientate the Tree according to it's drawing direction.

This is a rotation about the root node.