cal-layout 0.1.0.0 → 0.1.0.1
raw patch · 5 files changed
+40/−59 lines, 5 files
Files
- CHANGELOG.md +3/−0
- README.md +2/−21
- cal-layout.cabal +2/−2
- example/Bookings.hs +4/−6
- src/CalLayout.hs +29/−30
CHANGELOG.md view
@@ -1,4 +1,7 @@ # Revision history for cal-layout +## 0.1.0.1 -- 2019-01-03+* Second version.+ ## 0.1.0.0 -- 2019-01-03 * First version.
README.md view
@@ -1,12 +1,10 @@ # Calendar Layout Algorithm -This algorithm will calculate top, width, height, and width for each event in a list of events so that they can be drawn on a canvas such that none of them overlap.+This algorithm will calculate top, left, width and height for each event from a list of events so that they can be drawn on a canvas such that none of them overlap visually. ## Algorithm -The most complex bit in the algorithm is `CalLayout.mkIntersectionsForest`, which, given a list of calendar events produces a `Data.Tree.Forest`.--Given a list of events, and an _initial_ event (such that it intersects all events), `mkIntersectionsForest` will convert them to a forest such that every parent overlaps the children. This will produce a similar forest (by excluding the initial element):+The most complex bit in the algorithm is `CalLayout.insertEventTree` and `CalLayout.insertEventForest`, which, inserts an event into a tree or forest such that every parent overlaps the children. Afterwards given a list of events, `CalLayout.mkIntersectionsForest` will convert them to a forest by using the two functions above. This will produce a similar forest to: ``` > putStr $ drawForest $ map (fmap show) forest@@ -19,23 +17,6 @@ "12 days of Christmas workout" | `- "12 days of Christmas workout"-```--Otherwise, the tree really looks like:--```-> putStr $ drawTree $ fmap show (Node initial forest)-"root"-|-+- "P&P Leg Training"-| |-| `- "Gym Tour"-|-+- "12 days of Christmas workout"-|-`- "12 days of Christmas workout"- |- `- "12 days of Christmas workout" ``` Now that we have this structure, we need to calculate the `depth` and `maxDepth` of each node. `CalLayout.populateDepths` does exactly that. Viewed as a forest, it looks something like:
cal-layout.cabal view
@@ -1,5 +1,5 @@ name: cal-layout-version: 0.1.0.0+version: 0.1.0.1 synopsis: Calendar Layout Algorithm copyright: (c) 2019 Boro Sitnikovski homepage: https://github.com/bor0/cal-layout@@ -26,7 +26,7 @@ source-repository this type: git- tag: 0.1.0.0+ tag: 0.1.0.1 location: https://github.com/bor0/cal-layout library
example/Bookings.hs view
@@ -1,6 +1,6 @@ module Main where -import CalLayout+import CalLayout (getDimensions, CalEvent) data Booking = Booking { bCalId :: String@@ -8,15 +8,13 @@ , bEnd :: Int } deriving (Eq) -instance (CalLayout Booking) where+instance CalEvent Booking where start = bStart end = bEnd -instance (Show Booking) where+instance Show Booking where show (Booking id _ _) = show id -initial = Booking "root" minBound maxBound- events = [ Booking "Gym Tour" (10*60) (10*60 + 15) , Booking "P&P Leg Training" (10*60) (11*60)@@ -26,4 +24,4 @@ ] main :: IO ()-main = mapM_ print $ getDimensions events initial+main = mapM_ print $ getDimensions events
src/CalLayout.hs view
@@ -1,4 +1,4 @@-module CalLayout (CalLayout(..), Dimension, getDimensions) where+module CalLayout where import Data.List import Data.Tree@@ -6,7 +6,7 @@ type TimeUnit = Int -- | Main interface for events.-class (Eq a) => CalLayout a where+class (Eq a) => CalEvent a where start :: a -> TimeUnit end :: a -> TimeUnit @@ -19,33 +19,32 @@ } deriving (Show) -- | Insert an event into a tree by calculating intersections.-insertEvent :: (CalLayout a) => a -> Tree a -> Tree a-insertEvent e n@(Node t t') = if e `intersects` t then Node t (insertEventForest e t') else n- where- -- | Given two events, check if they intersect.- intersects :: (CalLayout a) => a -> a -> Bool- intersects e e' = (start e >= start e' && start e < end e')- || ((start e' == start e) || (end e' == end e))- -- | Given an event and a tree, check if the tree contains it.- treeContains :: (CalLayout a) => a -> Tree a -> Bool- treeContains e (Node e' []) = e == e'- treeContains e (Node e' trs) = e == e' || any (treeContains e) trs- -- | Insert an event in a forest.- insertEventForest :: (CalLayout a) => a -> Forest a -> Forest a- insertEventForest e [] = [Node e []]- insertEventForest e (x:xs) = let newx = insertEvent e x in- if treeContains e newx- then newx : xs- else x : insertEventForest e xs+insertEventTree :: (CalEvent a) => a -> Tree a -> Tree a+insertEventTree e n@(Node t t') = if e `intersects` t then Node t (insertEventForest e t') else n +-- | Given two events, check if they intersect.+intersects :: (CalEvent a) => a -> a -> Bool+intersects e e' = (start e >= start e' && start e < end e')+ || ((start e' == start e) || (end e' == end e))++-- | Given an event and a tree, check if the tree contains it.+treeContains :: (CalEvent a) => a -> Tree a -> Bool+treeContains e (Node e' []) = e == e'+treeContains e (Node e' trs) = e == e' || any (treeContains e) trs++-- | Insert an event in a forest.+insertEventForest :: (CalEvent a) => a -> Forest a -> Forest a+insertEventForest e [] = [Node e []]+insertEventForest e (t:ts) = let newTree = insertEventTree e t in+ if treeContains e newTree+ then newTree : ts+ else t : insertEventForest e ts+ -- | Make intersections forest by recursively using `insertEvent`. -- we need to provide an initial member since a `Data.Tree` cannot be empty.-mkIntersectionsForest :: (CalLayout a) => [a] -> a -> Forest a-mkIntersectionsForest events initial = go (sortBy startSort events) initialTree+mkIntersectionsForest :: (CalEvent a) => [a] -> Forest a+mkIntersectionsForest events = go (sortBy startSort events) [] where- -- | The initial tree contains a root node with least and most start/end times- -- for capturing all intersections.- initialTree = Node initial [] -- | startSort first sorts by start time, then length of events startSort e1 e2 | start e1 == start e2 = lengthSort e1 e2 | start e1 < start e2 = LT@@ -54,8 +53,8 @@ lengthSort e1 e2 | end e2 < end e1 = LT | otherwise = GT -- | Iterative function for constructing the forest- go [] (Node r f) = f -- skip `initial` root- go (e:es) forest = go es (insertEvent e forest)+ go [] forest = forest+ go (e:es) forest = go es (insertEventForest e forest) -- | For a given forest, populate max depth and depth -- we need those for calculating width/left respectively.@@ -71,7 +70,7 @@ populateDepth t = squish (calcDepth t) t [] -- | Calculate dimensions for a forest.-calculateDimensions :: (CalLayout a) => Forest a -> [(a, Dimension)]+calculateDimensions :: (CalEvent a) => Forest a -> [(a, Dimension)] calculateDimensions forest = go (populateDepths forest) where go [] = []@@ -87,5 +86,5 @@ height = fromIntegral $ end e - start e -- | Helper wrapper for getting dimensions.-getDimensions :: (CalLayout a) => [a] -> a -> [(a, Dimension)]-getDimensions events initial = calculateDimensions $ mkIntersectionsForest events initial+getDimensions :: (CalEvent a) => [a] -> [(a, Dimension)]+getDimensions events = calculateDimensions $ mkIntersectionsForest events