About Schedules

A schedule is simply an ordered set of closed, non-overlapping intervals. Each interval is represented by two endpoints,

   [a_i, b_i]

called the left and right endpoints respectively.

Because the intervals are ordered, it is always true that

   a_i  <  b_i
        -

Because the intervals do not overlap, it is always true that

   b_i  <  a_(i+1)

The following collections of intervals are all schedules.

   [1, 2]  [3.14, 3.14159]  [1.D5, 1.D6]
 
   [-4, 4] [7, 7.000000000001], [7.000000000002, 8]
 
   [1.1, 1.1]  [2.2, 3.3]  [17.17, 19.19]

Note that an interval may contain a single point. Such an interval is called a `singleton interval' and has length zero.

The points of a schedule that are not endpoints of one of its intervals are called the schedules interior points. Singleton intervals contain no interior points.

What are schedules for?

Although a schedule can contain intervals of any kind, PERCY uses them to keep track of intervals of time. In particular, a single schedule typically contains intervals during which some combination of constraints is satisfied. The various FIND commands, for instance, create schedules containing intervals during which certain geometric constraints are met. These schedules are then changed and combined with other schedules, each operation resulting in the creation of a new schedule, until the final set of intervals reflects some combination of constraints.

This strategy offers two main benefits.

1.

2.

Once created, a schedule can be changed in any number of ways. Two schedules can be combined to form a third schedule, using simple algebraic operations: union, intersection, difference, and complement. The intervals in a schedule can be lengthened or shortened, shifted, reduced to their endpoints, removed or merged according to size, or adjusted in a number of ways.

Documenting Schedules

Schedule names may be upto 32 characters in length. This gives you a lot of room to make up meaningful names for schedules. However, sometimes schedules require more description than can be deduced from a name. In such cases, you may attach up to 800 characters of text to a schedule. This text is called the schedule's annotation. All find commands attach default annotation to a schedule as do most unary and binary operations. However, if you wish to attach more meaningful annotation you may do so with the ANNOTATE command. The annotation of a schedule is stored and restored along with the intervals of the schedule whenever you EXPORT or IMPORT a schedule to or from disk.

Schedule limits

You can define up to 50 schedules at one time. Schedules can contain up to 10000 intervals. (A single schedule is large enough to hold severa Each has a name, which is assigned to the schedule at the time it is created.

Because the number of schedules is limited, and because the number of schedules used grows quickly as a session wears on, it is usually prudent to remove schedules (using the FORGET command) as soon as they are no longer needed. In particular, temporary schedules created by a procedure should be dropped by the procedure.

The default interval

You must give a name to every schedule that you create. There is also a default schedule, which has no name and which contains a single interval, called the `default interval'.

This default interval is used by the schedule COMPLEMENT command, and defines the default search interval for the various FIND commands. You may change the bounds of the default interval with the SET BOUNDS command.

Schedule overflow

Occasionally, the execution of a schedule command may result in more intervals than will fit within the space provided for a schedule. This condition is called a schedule overflow. When a schedule overflow occurs, the results of the search are lost and cannot be recovered.

Schedule management commands

The schedule management commands assist you in keeping track of the schedules that you create and use during your Percy sessions.

Schedule management commands do not affect the intervals in schedules; use the schedule manipulation commands (described in the following section) to do that. The complete set of schedule management commands is summarized below.

Summary of schedule management commands

ANNOTATE: ``attaches'' annotation to a schedule. This overwrites any previous annotation associated with the schedule including any default annotation attached when the schedule was created.

EXPORT: writes the contents of a schedule to a disk file.

FORGET SCHEDULE: removes a schedule from the schedule space.

IMPORT: reads the contents of a schedule from a disk file.

NEW SCHEDULE: creates a new schedule with one or more intervals with fixed separation between intervals.

SET BOUNDS: sets one or both endpoints of the default schedule.

SHOW SCHEDULE: displays a report containing the annotation associated with a schedule as well as the intervals of the schedule.

SHOW STATISTICS: creates a report that summarizes the statistical properties of a schedule.

SHOW LIST OF SCHEDULES: creates a report listing all schedules together with their ``span'' and annotation.

Schedule manipulation commands

Each schedule manipulation command changes the intervals contained in an existing schedule in some systematic way in order to create a new schedule. All of the commands have the form:

   LET name = <expression>

where the ''expression'' indicates the operation to be performed and the operand(s) of that operation.

The commands come in two flavors: unary and binary.

Unary commands

Unary commands operate on the intervals contained in a single schedule, called the input schedule.

ASSIGNMENT: copies the contents of one schedule to another.

COMPLEMENT: constructs the algebraic complement of the input schedule with respect to the default interval.

CONTRACT: reduces the size of each interval by a specified amount.

EXPAND: increases the size of each interval by a specified amount.

EXTRACT: extracts one or both endpoints from each interval.

FILL: merges adjacent intervals (by filling gaps between them).

FILTER: drops intervals smaller than a specified size.

SHIFT: moves each interval forward or backward by the same amount.

Binary commands

Binary commands combine the intervals in two separate input schedules to form a third schedule.

DIFFERENCE: constructs the algebraic difference of the intervals in a pair of schedules.

INTERSECT: constructs the algebraic intersection of the intervals in a pair of schedules.

SIFT: `sifts' the intervals in one schedule `through' the intervals in a second schedule, retaining only the ones that `fit'.

SUPPORT: `supports' the intervals in one schedule `on' the intervals in a second schedule, retaining only those that are fully supported.

UNION: constructs the algebraic union of the intervals in a pair of schedules.

Syntax

Unary syntax

The syntax of every unary command looks like

   LET @name = @name <operator> [arguments]

The first word is always LET followed by the name of the schedule that will be the result of the operation. The name of the result is followed by the equal sign `=' and the name of the schedule is to be manipulated---the operand. Unless the command is a simple assignment the operation follows the operand together with any arguments needed to complete the operation specification. to be performed: COMPLEMENT, CONTRACT, and so on.

The operand must exist before the command is executed. The result schedule may already exist, in which case it is overwritten; otherwise it is created by the command.

The result of the command is always created in a temporary schedule, which is copied to the output schedule after the operation has been completed successfully. Thus, the output schedule may overwrite the input schedule, as in the following example.

   LET TEST = TEST FILL 30 seconds;

The result of this operation will be the schedule TEST with gaps of 30 or fewer seconds filled in.

Binary syntax

The syntax of every binary command looks like

   LET @name = @name <operator> @name

As with unary operations, the first word is always LET followed by the name of t schedule that will be the result of the operation and an equal sign. This introductory phrase is followed by the names of the two schedules to be combined separated by the operation used to combine them.

The allowed operators are: UNION, INTERSECT, DIFFERENCE, SIFT INSIDE, SIFT THROU the abbreviations `+', `*', `-', `<', `<=', `>' respectively.

Both input schedules must exist before the command is executed. The output schedule may already exist, in which case it is overwritten; otherwise it is created by the command.

The output schedule may overwrite either of the input schedules, as in the following examples.

   LET GOOD = BETTER + GOOD;
   LET GOOD = GOOD   + BEST;

Redundant commands

Some of the schedule manipulation commands are redundant. For example, the CONTRACT and SHIFT operations can be implemented by judicious choice of inputs to the EXPAND command. In these cases, the extra commands are provided because their names are more straightforward.

Graphical descriptions

The description of each command is illustrated by a graphical description of the operation performed by the command, similar to the one shown below.

   Input schedule  :      ---     ---------   ---------       -
   Input schedule  :    -           -----    -----          -----
   Output schedule :    - ---     ---------  ----------     -----

Adjacent dashed lines are considered to be continuous intervals. The example above illustrates the union of two schedules, each of which contains four intervals. The resulting schedule contains five intervals.