Principle
The calendar is stored as a binary tree where leafs represent elementary time periods. Other nodes represent the period of time covered by all their descendants.
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.
A node of the binary tree is a "top-node" for a given reservation if
- 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.
The following value is stored in each node:
q(node) = max(q(left child), q(right child)) + total amount of reserved resource for all reservations having this node as a "top-node"(for code optimization, the two parts of this sum are usually stored separately.)
Read more about this topic: Top-nodes Algorithm
Famous quotes containing the word principle:
“The principle of fashion is ... the principle of the kaleidoscope. A new year can only bring us a new combination of the same elements; and about once in so often we go back and begin again.”
—Katharine Fullerton Gerould (1879–1944)
“There is no teaching until the pupil is brought into the same state or principle in which you are; a transfusion takes place; he is you, and you are he; then is a teaching; and by no unfriendly chance or bad company can he ever lose the benefit.”
—Ralph Waldo Emerson (1803–1882)
“Help thyself: then everyone will help thee too. Principle of Christian charity.”
—Friedrich Nietzsche (1844–1900)