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:
“For me chemistry represented an indefinite cloud of future potentialities which enveloped my life to come in black volutes torn by fiery flashes, like those which had hidden Mount Sinai. Like Moses, from that cloud I expected my law, the principle of order in me, around me, and in the world.... I would watch the buds swell in spring, the mica glint in the granite, my own hands, and I would say to myself: “I will understand this, too, I will understand everything.””
—Primo Levi (1919–1987)
“The only principle that does not inhibit progress is: anything goes.”
—Paul Feyerabend (1924–1994)
“If there be one principle more deeply rooted than any other in the mind of every American, it is that we should have nothing to do with conquest.”
—Thomas Jefferson (1743–1826)