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:
“I ... observed the great beauty of American government to be, that the simple machines of representation, carried through all its parts, gives facility for a being moulded at will to fit with the knowledge of the age; that thus, although it should be imperfect in any or all of its parts, it bears within it a perfect principle the principle of improvement.
”
—Frances Wright (1795–1852)
“The principle of asceticism never was, nor ever can be, consistently pursued by any living creature. Let but one tenth part of the inhabitants of the earth pursue it consistently, and in a day’s time they will have turned it into a Hell.”
—Jeremy Bentham (1748–1832)
“In case I conk out, this is provisionally what I have to do: I must clarify obscurities; I must make clearer definite ideas or dissociations. I must find a verbal formula to combat the rise of brutality—the principle of order versus the split atom.”
—Ezra Pound (1885–1972)