Top-nodes Algorithm - Principle

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.

Example of a 7-hour calendar (with elementary periods of one hour)

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.
Top-nodes for a reservation from 1:00 to 5:59

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:

    “Well, you Yankees and your holy principle about savin’ the Union. You’re plunderin’ pirates that’s what. Well, you think there’s no Confederate army where you’re goin’. You think our boys are asleep down here. Well, they’ll catch up to you and they’ll cut you to pieces you, you nameless, fatherless scum. I wish I could be there to see it.”
    —John Lee Mahin (1902–1984)

    “The monk in hiding himself from the world becomes not less than himself, not less of a person, but more of a person, more truly and perfectly himself: for his personality and individuality are perfected in their true order, the spiritual, interior order, of union with God, the principle of all perfection.”
    —Thomas Merton (1915–1968)

    “All Protestantism, even the most cold and passive, is a sort of dissent. But the religion most prevalent in our northern colonies is a refinement on the principle of resistance; it is the dissidence of dissent, and the Protestantism of the Protestant religion.”
    —Edmund Burke (1729–1797)