calendar-tiler - npm Package Compare versions

Comparing version 1.0.2 to 1.0.3

calendarTiler.js

		@@ -599,13 +599,11 @@ /global define, module, self/
		calculateBlockingDx: function CalendarTiler_positionBuilder_calculateBlockingDx(positions, path, index, x) {
		var i,
		blockingVertexIndex = unsetIndexSentinel;
		var i;

		for (i = index + 1; i < path.length; ++i) {
		if (positions[path[i]].x !== xSentinel) {
		blockingVertexIndex = i;
		break;
		return (positions[path[i]].x - x) / (i - index);
		}
		}

		return blockingVertexIndex > unsetIndexSentinel ? ((positions[path[blockingVertexIndex]].x - x) / (blockingVertexIndex - index)) : undefined;
		return undefined;
		},
		@@ -612,0 +610,0 @@ calculateNonBlockingDx: function CalendarTiler_positionBuilder_calculateDx(positions, path) {

package.json

		{
		"name": "calendar-tiler",
		"version": "1.0.2",
		"version": "1.0.3",
		"description": "Algorithm for tiling a calendar filled with appointments",
		"main": "index.js",
		"main": "calendarTiler.js",
		"dependencies": {},
		@@ -7,0 +7,0 @@ "devDependencies": {},

455

README.md

		@@ -1,15 +0,17 @@
		Calendar Tiler
		=================
		An algorithm for aesthetically displaying appointments/events on a calendar, with an implementation in JS.
		# Calendar Tiler #
		An algorithm for aesthetically displaying appointments/events on a calendar, implemented in JavaScript.

		Table of Contents
		=================

		# Table of Contents #
		* [Calendar Tiler](#calendar-tiler)
		* [Table of Contents](#table-of-contents)
		* [Why Do](#why-do)
		* [How Use](#how-use)
		* [Why](#why)
		* [Usage](#usage)
		* [Installation](#installation)
		* [API](#api)
		* [Examples](#examples)
		* [Using Default Tile Parameters](#using-default-tile-parameters)
		* [Passing User Defined Tile Parameters](#passing-user-defined-tile-parameters)
		* [Algorithm Preface](#algorithm-preface)
		* [Algorithm Overview](#algorithm-overview)
		* [Examples With Diagrams](@examples-with-diagrams)
		* [Algorithm Details](#algorithm-details)
		* [Building Columns](#building-columns)
		@@ -19,92 +21,228 @@ * [Building Alignments](#building-alignments)
		* [Building Time Respective Directed Acyclic Graphs](#building-time-respective-directed-acyclic-graphs)
		* [Diagrams](@diagrams)
		* [Conclusions](#conclusions)

		Why Do
		=================
		At work (https://fieldnimble.com/) we needed a way to display the calendars of many users all at once and have the appointments/visits/events/what-have-you render in a clean and aesthetically pleasing way. So I designed this algorithm and then implemented it in JS. It's gone through several iterations and eventually ended up the way it is now because it offers several aesthetic variations and performance options.
		# Why #
		At [work](https://www.pointmanhq.com/products/field-nimble) we needed a way to display the calendars of many users all at once and have the appointments/events/visits/what-have-you render in a clean and aesthetically pleasing way. So I designed what I thought was a good algorithm and then eventually realized there were several variations that could be made to give different visual flavors.

		How Use
		=================
		Using npm: (https://www.npmjs.com/package/calendar-tiler)
		* `npm install calendar-tiler`
		# Usage #
		CalendarTiler is written in ES5 following the [Universal Module Definition (UMD)](https://github.com/umdjs/umd) so that it can be used in the browser or in Node.js without needing to do any extra work. All the code exists in a single file,
		```
		calendar-tiler/calendarTiler.js
		```

		Please consult the example files to see the full process in action and to see how it could be used from start to finish.
		## Installation ##
		Using npm: [calendar-tiler](https://www.npmjs.com/package/calendar-tiler)
		```
		npm install calendar-tiler
		```

		## API ##
		There's only one public facing function, `calendarTiler.tileAppointments`, it can be called with two parameters,
		* `appointments` (Required) (Type: array[object]) objects to be tiled, each appointment needs to include 2 properties,
		1. `<START_VALUE>` (Type: number) specifying the start of the appointment
		2. `<END_VALUE>` (or `<DURATION_VALUE>`) (Type: number) specifying the end of the appointment (or the duration of the appointment), note that if you are not using durational units, then `<END_VALUE>` must be greater than `<START_VALUE>` and if you are using durational units then `<DURATION_VALUE>` must be greater than 0.
		* `tileParameters` (Type: object) that has 4 properties,
		1. `start` (Type: string - Default Value: `"start"`) which specifies the property `<START_VALUE>` for each appointment (e.g. `"start"`, `"startTime"`, `"startingTime"`, etc.)
		2. `delineator` (Type: string - Default Value: `"end"`) which specifies the property `<END_VALUE>` (or `<DURATION_VALUE>`) for each appointment (e.g. `"end"`, `"endTime"`, `"endingTime"`, `"duration"`, `"appointmentLength"` etc.)
		3. `usesDuration` (Type: Boolean - Default Value: `false`) which specifies that the `delineator` represents a durational unit as opposed to a time unit.
		4. `tilingMethod` (Type: string - Default Value: `fillSpace`) which specifies the way the appointments are tiled
		* `balanced` this indicates that each appointment should have the same width, it's the fastest of the three options since there are no graph calculations to make, though some of the appointments may not be as wide as they can be, which may leave the layout looking a little sparse in some cases.
		* `fillSpace` this indicates that each appointment should take up as much space as it possibly can while retailing a space efficient layout. It's slower than `balanced` since there are graph calculations to make, but it produces the most aesthetically pleasing result of the three options.
		* `timeRespective` this indicates that appointments with later start times should always appear as far to the left as possible. It's the slowest of the three options and the layout it produces is somewhat of an acquired taste (straight up ugly in cases with large numbers of appointments. Combining this with the slowness in computation using this method, makes me suspicious that reality has some inherent aesthetic bias towards other methods), but it's the most rigidly ordered of the three options.
		1. `appointments` (Required) (Type: Array[Object]) objects to be tiled, each appointment needs to include 2 properties,
		1. `<START_VALUE>` (Type: Number) specifying the start of the appointment
		2. `<END_VALUE>`/`<DURATION_VALUE>` (Type: Number) specifying the end of the appointment (or the duration of the appointment), note that if you are not using durational units, then `<END_VALUE>` must be greater than `<START_VALUE>` and if you are using durational units then `<DURATION_VALUE>` must be greater than 0.
		2. `tileParameters` (Type: Object) that has 4 properties,
		1. `start` (Type: String - Default Value: `'start'`) which specifies the property `<START_VALUE>` for each appointment (e.g. `'start'`, `'startTime'`, `'startingTime'`, etc.)
		2. `delineator` (Type: String - Default Value: `'end'`) which specifies the property `<END_VALUE>`/`<DURATION_VALUE>` for each appointment (e.g. `'end'`, `'endTime'`, `'endingTime'`, `'duration'`, `'appointmentLength'` etc.)
		3. `usesDuration` (Type: Boolean - Default Value: `false`) which specifies that the `delineator` represents a durational unit as opposed to a time unit.
		4. `tilingMethod` (Type: String - Default Value: `'fillSpace'`) which specifies the way the appointments are tiled
		1. `'balanced'` this indicates that each appointment should have the same width, it's the fastest of the three options since there are no graph calculations to make, though some of the appointments may not be as wide as they can be, which may leave the layout looking a little sparse in some cases.
		2. `'fillSpace'` this indicates that each appointment should take up as much space as it possibly can while retailing a space efficient layout. It's slower than `balanced` since there are graph calculations to make, but it produces arguably the most aesthetically pleasing result of the three options.
		3. `'timeRespective'` this indicates that appointments with later start times should always appear as far to the left as possible. It's the slowest of the three options and the layout it produces is somewhat of an acquired taste (straight up ugly in cases with large numbers of appointments. Combining this with the slowness in computation using this method, makes me suspicious that reality has some inherent aesthetic bias towards other methods), but it's the most rigidly ordered of the three options.

		The output is a single object with 2 properties,
		* `sortedAppointments` (Type: array[object]) containing the input appointments sorted into a new array by `start` ascending and `end` descending
		* `positions` (Type: array[object]) in the same order as the `sortedAppointments` order, each member contains 4 properties
		1. `x` (Type: number) the x-coordinate for where the sorted appointment should be placed on the x-axis
		2. `dx` (Type: number) the width for how wide the sorted appointment should be on the x-axis
		3. `y` (Type: number) the y-coordinate for where the sorted appointment should be placed on the y-axis (note is this just `start` of the appointment)
		4. `dy` (Type: number) the height for how tall the sorted appointment should be on the y-axis (note this is just `end` - `start` or `duration` for the appointment)
		1. `sortedAppointments` (Type: Array[Object]) containing the input appointments sorted into a new array by `start` ascending and `end` descending
		2. `positions` (Type: Array[Object]) in the same order as the `sortedAppointments` order, each member contains 4 properties
		1. `x` (Type: Number) the x-coordinate for where the sorted appointment should be placed on the x-axis
		2. `dx` (Type: Number) the width for how wide the sorted appointment should be on the x-axis
		3. `y` (Type: Number) the y-coordinate for where the sorted appointment should be placed on the y-axis (note is this just `start` of the appointment)
		4. `dy` (Type: Number) the height for how tall the sorted appointment should be on the y-axis (note this is just `end` - `start` or `duration` for the appointment)

		Please note that the `x` and `dx` values are normalized between 0 and 1, while the `y` and `dy` keep the units of the input appointments.

		Input Examples ...
		* Using default `tileParameters`,
		1. `appointments = [{ start: 0, end: 12 }, { start: 4.5, end: 6.75 }, { start: 13.25, end: 19.5 }]`
		* Passing `tileParameters`,
		1. `appointments = [{ wEirDsTart: 7.5, ohADuration: 21.25 }, { wEirDsTart: 14.25, ohADuration: 16.75 }, { wEirDsTart: 22, ohADuration: 23.75 }]`
		2. `tileParameters = { start: "wEirDsTart", delineator: "ohADuration", usesDuration: true, tilingMethod: "fillSpace" }`
		## Examples ##
		Please consult the example files to see the full process in action and to see how it could be used from start to finish.

		Algorithm Preface
		=================
		The algorithm works by accepting an array of appointments `A` as an input, where each appointment `a` has a start value `s_a` and an end value `e_a`. In principal `s_a` and `e_a` can be any real valued numbers with `s_a < e_a` (however `0 <= s_a < e_a <= 24` is an obvious use case).
		### Using Default Tile Parameters ###
		```javascript
		var appointments = [{
		start: 0,
		end: 12
		}, {
		start: 13.25,
		end: 19.5
		}, {
		start: 4.5,
		end: 6.75
		}],
		tiling = calendarTiler.tileAppointments(appointments);

		The goal of the algorithm is to produce an array called `Positions_A` which for each appointment `a` in `A` contains a 4-dimensional vector `positions_a = (y_a, dy_a, x_a, dx_a)` where
		* `x_a` is the horizontal position of the appointment
		* `dx_a` is the width of the appointment
		* `y_a` is vertical position of the appointment (Note: This is given by `s_a`)
		* `dy_a` is the height of the appointment (Note: This is either given by `e_a`, or it can be easily computed as `e_a - s_a` if inputs are in durational units.)
		/* Outputs:
		tiling = {
		sortedAppointments: [{
		start: 0,
		end: 12
		}, {
		start: 4.5,
		end: 6.75
		}, {
		start: 13.25,
		end: 19.5
		}],
		positions: [{
		x: 0,
		dx: 0.5,
		y: 0,
		dy: 12
		}, {
		x: 0.5,
		dx: 0.5,
		y: 4.5,
		dy: 2.25
		}, {
		x: 0,
		dx: 1,
		y: 13.25,
		dy: 6.25
		}]
		}
		*/
		```

		As previously noted, `x_a` and `dx_a` values are normalized between 0 and 1, while the `y_a` and `dy_a` keep the units of the input appointments. So that,
		* `0 <= x_a < 1` and `0 < dx_a <= 1`
		for each `a` in `A`.
		### Passing User Defined Tile Parameters ###
		```javascript
		var appointments = [{
		startingTime: 0,
		duration: 12
		}, {
		startingTime: 13.25,
		duration: 6.25
		}, {
		startingTime: 4.5,
		duration: 2.25
		}],
		tileParameters = {
		start: `startingTime`,
		delineator: `duration`,
		usesDuration: true,
		tilingMethod: `balanced`
		},
		tiling = calendarTiler.tileAppointments(appointments);

		The idea being that each appointment `a` can then be placed on the 2-dimensional `(x, y)` plane with the following set of points corresponding to a box that represents each appointment `a` (from upper-left, upper-right, lower-right, lower-left) in clockwise fashion,
		`Box_a = { (x_a, y_a), (x_a + dx_a, y_a), (x_a + dx_a, y_a + dy_a), (x_a, y_a + dy_a) }`
		/* Outputs:
		tiling = {
		sortedAppointments: [{
		startingTime: 0,
		duration: 12
		}, {
		startingTime: 4.5,
		duration: 2.25
		}, {
		startingTime: 13.25,
		duration: 6.25
		}],
		positions: [{
		x: 0,
		dx: 0.5,
		y: 0,
		dy: 12
		}, {
		x: 0.5,
		dx: 0.5,
		y: 4.5,
		dy: 2.25
		}, {
		x: 0,
		dx: 1,
		y: 13.25,
		dy: 6.25
		}]
		}
		*/
		```

		So how do we go about producing `Positions_A`? Since `y_a` and `dy_a` are already given we only need to find `x_a` and `dx_a` for each `a` in `A`.
		# Algorithm Preface #
		NOTE: All following psuedocode will use 1-based indexing on Lists/Arrays/Enumerable Collections (I don't feel like writing `list.Length - 1` or `array.Length - 1` a thousand times)

		Algorithm Overview
		==================
		As a convention for any `aaray` let,
		* `lastIndex` be the last index (i.e. `array.length - 1` for a 0-based array scheme and `array.length` for a 1-based array scheme).
		* `firstIndex` be the first index (i.e. 0 for a 0-based array scheme and 1 for a 1-based array scheme).
		The algorithm works by accepting an array of appointments `A` as an input, where each appointment `a` has a start value `a.start` and an end value `a.end`. In principal `a.start` and `a.end` can be any real valued numbers with `a.start < a.end` (however `0 <= a.start < a.end <= 24` is an obvious use case).

		Regardless of the selected tiling method (balanced, fill space or time respective), the first step is always the same.
		NOTE: Through abuse of notation, `collection[a]` means `collection[i]` where `a = A[i]`

		Sort `A` by the following rule,
		* `a <= b iff y_a < y_b or (y_a == y_b and dy_a >= dy_b)` for `a` and `b` in `A`
		This sorting simply means that appointments are sorted in ascending fashion by start time and then in descending fashion by duration should they have equal start times.
		NOTE: From now on we'll just assume that `A` is sorted as above.
		The goal of the algorithm is to produce an array called `positions` which for each appointment `a` in `A` contains a 4-dimensional vector `position[a] = {x, dx, y, dy}` where
		* `x` is the horizontal position of the appointment `a`
		* `dx` is the width of the appointment `a`
		* `y` is vertical position of the appointment `a` (Note: This is given by `a.start`)
		* `dy` is the height of the appointment `a` (Note: This is either given by `a.end`, or it can be easily computed as `a.end - a.start` if inputs are not durational units.)

		After the sorting step, we move onto one of 3 subroutines each corresponding to one of the 3 different tiling method.
		As previously noted, for each `a` in `A`, `positions[a].x` and `positions[a].dx` values are normalized between 0 and 1, while the `positions[a].y` and `positions[a].dy` keep the units of the input appointments.
		```
		0 <= positions[a].x < 1
		0 < positions[a].dx <= 1
		```
		The idea being that each appointment `a` can then be placed on the 2-dimensional `(x, y)` plane with the following set of points corresponding to a box that represents each appointment `a` (from upper-left, upper-right, lower-right, lower-left) in clockwise fashion,
		```
		{
		(positions[a].x, positions[a].y),
		(positions[a].x + positions[a].dx, positions[a].y),
		(positions[a].x + positions[a].dx, positions[a].y + positions[a].dy),
		(positions[a].x, positions[a].y + positions[a].dy)
		}
		```
		So how do we go about producing `positions`? Since `positions[a].y` and `positions[a].dy` are already given (or easily computed using the `a.start` and `a.end` we only need to find `positions[a].x` and `positions[a].dx` for each `a` in `A`.

		The balanced and fill space tiling methods both begin the same way.
		* We generate an array of columns, each column is an array of appointments which are stacked on top of each other, with new columns being generated when an appointment cannot be stacked in a previous column without a collision between another appointment in that column.
		# Algorithm Overview #
		NOTE: We'll also assume that for each appointment `a`, `a.end` is using absolute units (as opposed to duration units).

		The time respective method generates what can best be described as alignments as opposed to the columns in the other methods.
		* The alignments are a series of rules which describe how one appointment "locks in" other appointments with respect to the appointments before and after it in the sort order.
		Regardless of the selected tiling method (balanced, fill space or time respective), the first step is always the same, the appointments are sorted in ascending fashion by start time and then in descending fashion by end time/duration should they have equal start times. After the sorting occurs we initialize the `positions` array as follows,
		```
		InitializePositions(A)
		IN: A - An array of appointments each with a start and an end property,
		which are decimal numbers such that, start < end.
		OUT: postions - An array (with the same length as A) of 4-tuples, (x, dx, y, dy).
		Each of x, dx, y and dy are decimal numbers where,
		0 <= x < 1 and 0 < dx <= 1
		1. SET positions = new Array[A.Length]
		2. SET A = CALL A.Sort(CompareAppointments)
		3. FOR i = 1 TO A.Length DO
		4. SET positions[i] = {
		5. x: 0,
		6. dx: 1,
		7. y: A[i].start,
		8. dy: A[i].end - A[i].start
		9. }
		10. ENDFOR
		11. RETURN positions

		NOTE: The procedures for obtaining the columns/alignments are detailed in [Building Columns](#building-columns) and [Building Alignments](#building-alignments) respectively.
		CompareAppointments(appointment1, appointment2)
		IN: appointment1, appointment2 - Appointments with start and end properties where,
		start and end are decimal numbers such that start < end.
		OUT: isLessThan - A boolean value which is TRUE if appointment1 <= appointment2 and FALSE otherwise.
		1. SET isLessThan = FALSE
		2. IF appointment1.start < appointment2.start THEN
		3. isLessThan = TRUE
		4. ELSE IF appointment1.start == appointment2.start AND appointment1.end >= appointment2.end THEN
		5. isLessThan = TRUE
		6. ENDIF
		7. RETURN isLessThan
		```
		After the initialization step, we move onto one of 3 subroutines each corresponding to one of the 3 different tiling method.

		The balanced and fill space tiling methods both begin the same way. We generate an array of columns, each column is an array of appointments which are stacked on top of each other, with new columns being generated when an appointment cannot be stacked in a previous column without a collision between another appointment in that column. Details for the procedure to construct said columns can be found here [Building Columns](#building-columns).

		The time respective method generates what can best be described as alignments as opposed to the columns in the other methods. The alignments are a series of rules which describe how one appointment "locks in" other appointments with respect to the appointments before and after it in the sort order. Details for the procedure to construct said alignments can be found here [Building Alignments](#building-alignments).

		In the case of the balanced method the `x` and `dx` values are easily computed using the columns by proceeding as follows,
		* Iterate over the columns, `x_a = index / columns.length` for all `a` in `columns[index]`
		* `dx_a = 1 / columns.length` for all `a` in `columns[index]`
		```
		CalcuatePositionsForBalancedTilingMethod(positions, columns)

		At this point the balanced method is finished and `Positon_A` is complete.
		1. SET columnsLength = columns.Length
		2. FOR i = 1 TO columns.Length DO
		3. FOR j = 1 TO columns[i].Length
		4. SET positions[i].x = i / columnsLength
		5. SET positions[i].dx = 1 / columnsLength
		6. ENDFOR
		7. ENDFOR
		```
		At this point the balanced method is finished and `positions` is complete. The user could now display the appointments on screen using the given `positions` array.

		@@ -115,50 +253,147 @@ In the case of the fill space and time respective methods, it's a bit more complicated. The first step is to create two Directed Acyclic Graphs (DAG for short) using either the columns or alignments. The procedures for building these can be found in [Building Fill Space Directed Acyclic Graphs](#building-fill-space-directed-acyclic-graphs) and [Building Time Respective Directed Acyclic Graphs](#building-time-respective-directed-acyclic-graphs) respectively. The first DAG, will be referred to as `backward` and is constructed by moving through the columns or alignments backwards. The second DAG, will be referred to as `forward` and is constructed by moving through the columns in ascending fashion.

		Once the two DAGs are constructed, we build a Topological Ordering on the vertices in each DAG so that they can be easily traversed to find the longest path through `a` in each DAG for each `a` in `A`. The longest traversal through `a` from `backward` is combined with the longest traversal through `a` from `forward` to create `longest_traversal_a`, which is an array of appointment indices in a particular order (namely the Topological Ordering). The set of such traversal is `Longest_Traversals_A` which is the set of distinct `longest_traversal_a` and is sorted so that the longest traversals come first.
		Once the two DAGs are constructed, we build a Topological Ordering on the vertices in each DAG so that they can be easily traversed to find the longest path through `a` in each DAG for each `a` in `A`. Then we generate the distinct longest traversals as follows,
		```
		GenerateLongestDagTraversals(positions, dags)
		1. SET longestDagTraversals = new List
		2. SET traversalKeys = new Map
		3. SET longestDagTraversal = NULL
		4. SET traversalKey = NULL
		5. FOR i = 1 TO positions.Length
		6. SET longestDagTraversal = dags.backward.GetLongestTraversalThroughVertex(i).Reverse()
		7. longestDagTraversal.Add(i)
		8. longestDagTraversal.AddRange(dags.forward.GetLongestTraversalThroughVertex(i))
		9. SET traversalKey = longestDagTraversal.Join(',')
		10. IF traversalKeys.Find(traversalKey) != NULL
		11. traversalKeys.Add(traversalKey, TRUE)
		12. longestDagTraversals.Add(longestDagTraversal)
		13. ENDIF
		14. ENDFOR
		15. RETURN longestDagTraversals.Sort(CompareDagTraversalLengths)

		CompareDagTraversalLengths(dagTraversal1, dagTraversal2)
		1. RETURN dagTraversal2.Length > dagTraversal1.Length

		List.Join(delineator)
		1. SET joined = new String
		2. FOR i = 1 TO THIS.Length
		3. joined.Concatenate(THIS[i].ToString())
		4. IF i < THIS.Length
		5. joined.Concatenate(delineator)
		6. ENDIF
		7. ENDFOR
		8. RETURN joined
		```
		The point of doing this is, is so that we can easily assign an `x` and `dx` value to each appointment based on its position in the traversals. The procedure for doing this is as follows,
		* Iterate over `Longest_Traversals_A` using the sort order (longest traversals first) by `i`
		* Let `traversal = Longest_Traversals_A[i]`
		1. Iterate over `traversal` by `j`
		2. Then for each appointment `a` in `traversal`
		* Let `previous = j > 0 ? traversal[j - 1] : null`
		* `x_a = previous == null ? 0 : x_previous + dx_previous`
		* Set `dx = calculateBlockingDx(traversal, j, x_a)`
		1. ... insert subroutine
		* If `x_a == 0` then `dx_a` = `dx != null ? dx : calculateNonBlockingDx(traversal)`
		1. ... insert subroutine
		```
		CalcuatePositionsUsingLongestDagTraversals(positions, longestDagTraversals)
		1. SET a = NULL
		2. SET beforeA = NULL
		3. SET x = 0
		4. SET dx = NULL
		5. FOR i = 1 TO longestDagTraversals.Length
		6. SET traveral = longestDagTraversals[i]
		7. FOR j = 1 TO traversal.Length
		8. SET a = traversal[j]
		9. IF j > 1
		10. SET beforeA = traversal[j - 1]
		11. SET x = positions[beforeA].x + positions[beforeA].dx
		12. ELSE
		13. SET x = 0
		14. ENDIF
		15. SET dx = CalculateBlockingDx(positions, traversal, j, x)
		16. IF positions[a].x == 0
		17. SET positions[a].x = x
		18. IF dx != NULL
		19. SET positions[a].dx = dx
		20. ELSE
		21. SET positions[a].dx = CalculateNonBlockingDx(positions, traversal)
		22. ENDIF
		23. ENDIF
		24. ENDFOR
		25. ENDFOR

		Thus we have computed `x_a` and `dx_a` for each `a` in `A` and so `Postions_A` is complete.
		CalculateBlockingDx(positions, traversal, index, x)
		1. FOR i = index + 1 TO traversal.Length
		2. IF positions[traversal[i]].x == 0
		3. RETURN positions[traversal[i]].x - x) / (i - index)
		4. ENDIF
		5. ENDFOR
		6. RETURN NULL

		Examples With Diagrams
		======================
		CalculateNonBlockingDx(positions, traversal)
		1. SET unset = 0
		2. SET dx = 0
		3. FOR i = 0 TO traversal.Length
		4. IF positions[traversal[i]].dx < 1
		5. SET dx = dx + positions[traversal[i]].dx
		6. ELSE
		7. INCREMENT unset
		8. ENDIF
		9. ENDFOR
		10. IF unset == 0
		11. SET unset = 1
		12. ENDIF
		13. RETURN (1 - dx) / unset
		```
		The essence of this procedure is trying to fill out the longest traversals first to ensure these appointments receive the proper `x` and `dx` values first. If there are appointments ahead of a given appointment `a` in the traversal which have has their `x` and `dx` values then `a` will have restricted `x` and `dx` values. If there are no appointments ahead of `a` in the traversal which have already been assigned `x` and `dx` values then we need to provision space for those appointments so they will have enough space when their assignments come.

		Building Columns
		================
		Thus we have computed `positions[a].x` and `positions[a].dx` for each `a` in `A` and so `positions` is complete. The user could now display the appointments on screen using the given `positions` array.

		# Algorithm Details #
		## Building Columns ##
		Building the columns is very straightforward, essentially we just try to keep pushing appointments to the foremost available column as follows,
		```
		ConstructColumns(A)
		1. SET columns = new List
		2. columns.Add(new List)
		3. columns[1].Add(A[1])
		4. FOR i = 1 TO A.Length
		5. FOR j = 1 TO columns.Length
		6. SET column = columns[j]
		7. IF A[i].start >= column[column.Length].end
		8. column[j].Add(A[i])
		9. column = NULL
		10. BREAK
		11. ENDIF
		12. ENDFOR
		13. IF column != NULL
		14. columns.Add(new List)
		15. columns[columns.Length].Add(A[i])
		16. ENDIF
		17. ENDFOR
		18. RETURN columns
		```

		* Initialize `columns = [[A[firstIndexx]]]``
		* For each `a` in `A`,
		1. For each `column` in `columns`
		2. If `s_a` >= `e_column[lastIndex]` add `a` to end of `column`
		3. Else if `a` was not added to any column then add a new column `[a]` to `columns`
		## Building Alignments ##
		```
		```

		Building Alignments
		===================
		## Building Fill Space Directed Acyclic Graphs ##
		After computing the columns ([Building Columns](#building-columns)) building the DAG isn't too difficult.
		```
		```

		Building Fill Space Directed Acyclic Graphs
		===========================================
		## Building Time Respective Directed Acyclic Graphs ##
		After computing the alignments ([Building Alignments](#building-alignments)) building the DAGs is very straightforward.
		```
		BuildTimeRespectiveDAG(A, alignments)
		1. SET forward = new Dag(A.Length)
		2. SET backward = new Dag(A.Length)
		3. FOR i = 1 TO A.Length
		4. FOR j = 1 TO A.Length
		5. IF alignments.rFront[A[j]][1] === A[i]
		6. backward.AddEdge(A[i], A[j])
		7. ENDIF
		8. IF alignments.rBack[A[j]][alignments.rBack[A[j].Length] === A[i]
		9. forward.AddEdge(A[i], A[j])
		10. ENDIF
		11. ENDFOR
		12. ENDFOR
		13. RETURN (backwardDag, forwardDag)
		```

		Building Time Respective Directed Acyclic Graphs
		================================================
		After computing the alignments (#building-alignments) building the DAGs is very straightforward.
		## Diagrams ##
		We'll use the following set of appointments

		As a reminder there are two DAGs (`backward` and `forward`).

		* For each `a` in `A`
		1. For each `b` in `A`
		* If `alignments.rFront[b][firstIndex] === a` add an edge to `backward` from `a` to `b`
		* If `alignments.rBack[b][lastIndex] === a` add an edge to `forward` from `a` to `b`

		Conclusions
		==============
		# Conclusions #
		More to come (namely specific implementation choices), you can examine the code (and/or example files) first though if you don't feel like waiting ;)

example/example.css

Sorry, the diff of this file is not supported yet

calendar-tiler - npm Package Compare versions

Improved metrics