{
  "path": "/posts/calendar-tetris-pt-2",
  "site": "at://did:plc:pans3xjam4khj7y54dx7gtfg/site.standard.publication/3mdqevmg6w32c",
  "tags": [
    "rust",
    "petgraph",
    "graphs",
    "WASM"
  ],
  "$type": "site.standard.document",
  "title": "Calendar Tetris: Representation Matters",
  "description": "Using Petgraph's directed graph to model overlapping calendar events instead of self-referential types in Rust.",
  "publishedAt": "2023-02-12T08:49:25.000Z",
  "textContent": "Live | Repository\n\nToo many events all at once\nLet'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.\n\nTo 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.\n\n!block_30_120\n\n!block_30_120_block_60_90\n\nThe recursion trap\nSelf-referential data types are more intuitive for modeling relationships between calendar nodes.\n\nAll calendar events can be represented by a handful of properties:\n\nForward traversal can be achieved elegantly by:\n\nHowever, 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.\n\nRust implementation of self-referential CalendarBlock:\n\nI 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.\n\nAdjacency List\nPetgraph has a clean API and we're going to use a directed graph to represent the calendar block tree.\n\nSo now the we can get rid of the RefCell.\n\nTraversal\n\nPetgraph'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).\n\nForward traversal is useful for calculating stack position, and backward traversal is useful for calculating the sub-tree depth (also called height) of each node.\n\nOur first algorithm does not require the sub-tree depth so we'll start there.\n\nStacking blocks\nWhen 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:\n- compare the new block with existing blocks starting from the root\n- 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)\n- if the events do not overlap we check the next event in the list of neighbors for an overlap\n\t- if no overlaps found the event gets added at the end (sorting helps here as well)\n\nTo determine whether a calendar block overlaps with another I added a method to the CalendarBlock struct:\n\nCalendar tree with stack position\nThis section is a WIP.",
  "canonicalUrl": "https://afloat.boats/posts/calendar-tetris-pt-2"
}