Calendar Tetris: Representation Matters

Live | Repository

Too many events all at once Let's assume that we want to stack two calendar blocks, block_1 starts at 12:30 AM and ends at 02:00 AM, and block_2 starts at 01:00 AM and ends at 01:30 AM. To simplify things however, let's just use their start and end times as minutes i.e. an event that starts at 12:30 AM would just be starting at minute 30.

To display the blocks we're going to use their start time as a top offset. Assuming that the day starts at minute 0, a block that starts at minute 30 will have a 30 px offset from the top. Keeping the page height in sync with the minutes in the day will make the offset math convenient.

!block_30_120

!block_30_120_block_60_90

The recursion trap Self-referential data types are more intuitive for modeling relationships between calendar nodes.

All calendar events can be represented by a handful of properties:

Forward traversal can be achieved elegantly by:

However, the Rust compiler needs to know the size of objects at compile time. As it's impossible to determine the size of self-referential data types, we have to use RefCells to model the CalendarBlocks.

Rust implementation of self-referential CalendarBlock:

I didn't want to do that as it seemed "un-idiomatic", and decided to use a separate adjacency list using Petgraph to store the calendar block tree instead.

Adjacency List Petgraph has a clean API and we're going to use a directed graph to represent the calendar block tree.

So now the we can get rid of the RefCell.

Traversal

Petgraph's edges_directed API returns an iterator over EdgeReference. EdgeReference has methods to retrieve the source, target, and weight of a particular edge. We can use edges_directed to find edges in both directions forward and backward (used later).

Forward traversal is useful for calculating stack position, and backward traversal is useful for calculating the sub-tree depth (also called height) of each node.

Our first algorithm does not require the sub-tree depth so we'll start there.

Stacking blocks When populating the tree I had to make sure that the calendar blocks are added in the right place. For simplicity I populate the tree every time a block is added/moved. As the blocks get sorted before the tree is populated we can create the correct hierarchy using the following rules:

• compare the new block with existing blocks starting from the root
• if the events overlap the event that starts later will be deeper in the tree (as we start with a sorted list this will always be the new block)
• if the events do not overlap we check the next event in the list of neighbors for an overlap
  • if no overlaps found the event gets added at the end (sorting helps here as well)

To determine whether a calendar block overlaps with another I added a method to the CalendarBlock struct:

Calendar tree with stack position This section is a WIP.