### 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.

### 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:

```
// using typescript to write pseudocode
interface CalendarBlock {
id: number
startMinute: number
endMinute: number
blockType: 'busy' | 'available'
children: CalendarBlock[]
}
```

Forward traversal can be achieved elegantly by:

```
currentBlock = currentBlock.children[0];
```

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 `RefCell`

s to model the `CalendarBlock`

s.

Rust implementation of self-referential CalendarBlock:

```
enum CalendarBlockType {
Busy,
Available,
}
struct CalendarBlock {
id: u32,
startMinute: u32,
endMinute: u32,
blockType: BlockType
children: Vec<RefCell<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`

.

```
struct CalendarBlock {
startMinute: u32,
endMinute: u32,
blockType: BlockType,
}
type Weight = usize;
pub struct CalendarBlockTree {
root_idx: NodeIndex,
adjacency_list: Graph<u32, Weight>,
}
fn main() {
let calendar_block_1 = CalendarBlock {
id: 1,
startMinute: 30,
endMinute: 120,
blockType: CalendarBlockType::Available,
};
let calendar_block_2 = CalendarBlock {
id: 2,
startMinute: 60,
endMinute: 90,
blockType: CalendarBlockType::Available,
};
let adjacency_list = Petgraph::Graph::new();
let node_1_idx = adjacency_list.add_node(calendar_block_1.id);
let node_2_idx = adjacency_list.add_node(calendar_block_2.id);
// add_edge takes the source, destination, and weight as params
adjacency_list.add_edge(node_1_idx, node_2_idx, 1);
// now that the nodes and edges are in place we can instantiate our CalendarBlockTree
let calendar_block_tree = CalendarBlockTree {
root_idx: node_1_idx,
adjacency_list,
};
}
```

### 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).

```
let forward_neighbors_list: Vec<petgraph::graph::EdgeReference<usize>> = self
.adjacency
.edges_directed(destination, petgraph::Direction::Outgoing)
.collect();
// unwrap is a story we're not going to tell today
let node_index = forward_neighbors.first().unwrap();
let calendar_block_2_from_adjacency_list = adjacency_list[node_idx];
assert_eq(calendar_block_2.id, calendar_block_2_from_adjacency_list.id);
```

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:

```
impl CalendarBlock {
pub fn does_overlap(&self, block: CalendarBlock) -> Option<CalendarBlockOverlap> {
if self.start_minute >= block.end_minute || self.end_minute < block.start_minute {
return None;
}
if self.start_minute > block.start_minute
|| (self.start_minute == block.start_minute && self.end_minute <= block.end_minute)
{
return Some(CalendarBlockOverlap::GetsSwallowed);
}
Some(CalendarBlockOverlap::Swallows)
}
}
```

### Calendar tree with stack position

This section is a WIP.