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:
“... it is not the color of the skin that makes the man or the woman, but the principle formed in the soul. Brilliant wit will shine, come from whence it will; and genius and talent will not hide the brightness of its lustre.”
—Maria Stewart (1803–1879)
“A certain secret jealousy of the British Minister is always lurking in the breast of every American Senator, if he is truly democratic; for democracy, rightly understood, is the government of the people, by the people, for the benefit of Senators, and there is always a danger that the British Minister may not understand this political principle as he should.”
—Henry Brooks Adams (1838–1918)
“Life is a game in which the rules are constantly changing; nothing spoils a game more than those who take it seriously. Adultery? Phooey! You should never subjugate yourself to another nor seek the subjugation of someone else to yourself. If you follow that Crispian principle you will be able to say “Phooey,” too, instead of reaching for your gun when you fancy yourself betrayed.”
—Quentin Crisp (b. 1908)