Top-nodes algorithm: Difference between revisions

Revision as of 20:00, 4 December 2021

Latest revision as of 13:34, 5 October 2022

Line 9:

==Principle==

The calendar is stored as a [[binary tree]] where leaves represent elementary time periods. Other nodes represent the period of time covered by all their descendants.

<center>[[File:AlgoRayroleArbre.svg|center|Example of a seven-hour calendar (with elementary periods of one hour)]]</center>

<{{center>|''Example of a seven-hour calendar (with elementary periods of one hour)''</center>}}

The period of time covered by a reservation is represented by a set of "top-nodes". This set is the minimal set of nodes that exactly cover the reservation period of time.

Line 17:

* all its descendants are inside the reservation period of time, and

* it is the root node, or at least one descendant of the parent node is outside of the reservation period of time.

<center>[[File:AlgoRayroleResa.svg|center|Top-nodes for a reservation from 1:00 to 5:59]]</center>

<{{center>|''Top-nodes for a reservation from 1:00 to 5:59''</center>}}

The following value is stored in each node: