Index Page

Window Routines in SPICELIB

   Window Routines in SPICELIB
         Revisions
      Overview
         Concepts
         Usage
         Naming Conventions
      Routines
         Unary Routines
         Binary Routines
         Complement Routines
         Comparison Routines
         Initialization Routines
      Summary

Window Routines in SPICELIB

Top

Revisions

September 3, 2002

Minor changes of wording were made.

Top

Overview

The SPICELIB window data type is intended to allow Fortran double precision cells to be used to manipulate continuous intervals of the real line. The window routines in the SPICELIB library are designed to simplify the use of this data type in Fortran programs.

By definition, a window is a double precision SPICE cell that contains zero or more intervals. An interval is an ordered pair of numbers,

   [ a(i), b(i) ]

such that

   a(i)  <  b(i)
         -

The intervals within a window are both ordered and disjoint. That is, the beginning of each interval is greater than the end of the previous interval:

   b(i)  <  a(i+1)

This restriction is enforced primarily because it allows window operations to be carried out efficiently.

The intervals stored in windows typically represent intervals of time (seconds, days, or centuries past a reference epoch). However, windows can represent any kinds of intervals.

Top

Concepts

The concept of ``measure'' is used to define the operations performed by the window routines. Intuitively, the measure of an interval is the ``length'' of the interval---that is, the difference of its endpoints:

   m(i) = b(i) - a(i)

Note that the singleton interval

   [ a(i), a(i) ]

has measure zero. The window

   [1,2], [4,9], [16,16]

contains intervals of measure 1, 5, and 0 respectively.

The concept of measure extends readily to the gaps between adjacent intervals. In the example above, the window contains gaps of measure 2 and 7. Intervals separated by gaps of measure zero or less are said to overlap. Overlapping intervals created by the window routines are merged as soon as they are created.

Finally, the measure of a window is the sum of the measures of its intervals. In the example above, the measure of the window is 6. Note that a floating point window containing only singletons has measure zero.

Top

Usage

Because windows are implemented as cells, any restriction that applies to the use of cells applies to the use of windows as well. For example, the size and cardinality of a window must be initialized (using the cell routines SSIZED and SCARDD) before the window may be used by any of the SPICELIB window routines. In addition, any of the general cell routines in SPICELIB may be used with windows. For example, COPYD may be used to copy the contents of one window into another, and the CARDD function may be used to determine the number of endpoints (that is, twice the number of intervals) in a window.

All errors are reported via standard SPICELIB error handling.

With the exception of the initialization routines, all window routines assume that input cells do in fact contain valid windows---that is, ordered and distinct sets of endpoints. Errors resulting from attempts to operate on invalid windows are not flagged.

Top

Naming Conventions

The names of window routines in SPICELIB are assigned as follows. Each name is of the form WNfffD, where fff is a three-letter mnemonic code indicating the function of the routine. For example, WNINTD computes the INTersection of two windows.

Top

Routines

The window routines in SPICELIB fall into the following categories.

--

Each category is discussed separately.

Top

Unary Routines

Each unary routine operates on a single window. Six unary operations are supported, each of which alters the contents of the input window. The calling sequences are shown below.

   WNCOND ( LEFT, RIGHT, WIN )        { Contract }
 
   WNEXPD ( LEFT, RIGHT, WIN )        { Expand }
 
   WNEXTD ( SIDE, WIN )               { Extract }
 
   WNFILD ( SMALL, WIN )              { Fill }
 
   WNFLTD ( SMALL, WIN )              { Filter }
 
   WNINSD ( LEFT, RIGHT, WIN )        { Insert }

Note that each of the unary window routines works in place. That is, only one window, WIN, appears in each calling sequence, serving as both input and output. Windows whose original contents need to be preserved should be copied prior to calling any of the unary routines.

WNINSD inserts the interval whose endpoints are LEFT and RIGHT into the window WIN. If the input interval overlaps any of the intervals in the window, the intervals are merged. Thus, the cardinality of WIN can actually decrease as the result of an insertion.

WNEXPD and WNCOND expand (lengthen) and contract (shorten) each of the intervals in the window WIN. The adjustments are not necessarily symmetric. That is, WNEXPD works by subtracting LEFT units from the left endpoint of each interval and adding RIGHT units to the right endpoint of each interval. WNCOND is the same as EXP with the signs of the arguments reversed, and is primarily provided for clarity in coding. (Expansion by negative increments is a messy concept.) Intervals are merged when expansion causes them to overlap. Intervals are dropped when they are contracted by amounts greater than their measures.

WNFLTD and WNFILD remove small intervals and small gaps between adjacent intervals. Both routines take as input a minimum measure, SMALL. WNFLTD filters out (drops) intervals with measures less than or equal to SMALL, while WNFILD merges adjacent intervals separated by gaps with measures less than or equal to SMALL.

Depending on the value of SIDE, WNEXTD extracts the left ('L') or right ('R') endpoints each interval in the window WIN. The resulting window contains only the singleton intervals

   [ a(1), a(1) ], ..., [ a(n), a(n) ]

   [ b(1), b(1) ], ..., [ b(n), b(n) ]

Top

Binary Routines

Binary routines operate on two input windows to produce a third (distinct) output window. Three major binary operations are supported. The calling sequences are shown below.

   WNUNID ( A, B, C )          { Union }
 
   WNINTD ( A, B, C )          { Intersection }
 
   WNDIFD ( A, B, C )          { Difference }

In contrast with the unary routines, none of the binary routines work in place. The output window (C) must be distinct from both of the input windows (A and B). We will have more to say about this later on.

WNUNID places the union of A and B into C. The union of two windows contains every point that is contained in the first window, or in the second window, or in both windows.

WNINTD places the intersection of A and B into C. The intersection of two windows contains every point that is contained in the first window AND in the second.

WNDIFD places the difference of A and B into C. The difference of two windows contains every point that is contained in the first window, but NOT in the second.

In each case, if the output window (C) is not large enough to hold the result of the operation, as many intervals as will fit are inserted into the window, and an error is signaled.

In each of the binary routines, the output window must be distinct from both of the input windows. All three of the binary operations can, in principle, be performed in place, but not all can be performed efficiently. Consequently, for the sake of consistency, none of the routines work in place. For example, the following calls are invalid.

   CALL WNINTD ( A, B, A )
   CALL WNINTD ( A, B, B )

In each of the examples above, whether or not the subroutine signals an error, the results will almost certainly be wrong. Nearly the same effect can be achieved, however, by placing the result into a temporary window, which is immediately copied back into one of the input windows, as shown below.

   CALL WNINTD ( A,    B, TEMP )
   CALL COPYD  ( TEMP, A,      )

Top

Complement Routines

WNCOMD determines the complement of a window with respect to an interval. The calling sequence is

   WNCOMD ( LEFT, RIGHT, A, C )       { Complement }

As with the binary routines, the output window (C) must be distinct from the input window (A).

Mathematically, the complement of a window contains those points that are not contained in the window. That is, the complement of the set of closed intervals

   [ a(1), b(1) ], [ a(2), b(2) ], ..., [ a(n), b(n) ]

is the set of open intervals

   ( -inf, a(1) ), ( b(1), a(2) ), ..., ( b(n), +inf )

Because Fortran offers no satisfactory way to represent infinity, WNCOMD must take the complement with respect to a finite interval.

In addition, because the results of a window routine must be another window, WNCOMD returns the closure of the set theoretical complement. In short, the double precision complement of the window

   [ a(1), b(1) ], [ a(2), b(2) ], ..., [ a(n), b(n) ]

with respect to the interval from LEFT to RIGHT is the intersection of the windows

   ( -inf, a(1) ], [ b(1), a(2) ], ..., [ b(n), +inf )

and

   [ LEFT, RIGHT ]

Note that intervals of measure zero (singleton intervals) in the original window are replaced by gaps of measure zero, which are filled. Thus, complementing a window twice does not necessarily yield the original window.

Top

Comparison Routines

Comparison routines allow the contents of windows to be compared against the contents of other windows. There are four routines: three logical functions and one subroutine. The calling sequences are shown below.

   WNELMD ( POINT, WIN )                      { Element }
 
   WNINCD ( LEFT, RIGHT, WIN )                { Inclusion }
 
   WNRELD ( A, OP, B )                        { Relation }
 
   WNSUMD ( WIN,
            MEAS,  AVG, STDDEV,
            SHORT, LONG         )             { Summary }

WNELMD, the simplest of the three, is true whenever the input point, POINT, is an element of the input window, WIN---that is, whenever the point lies within one of the intervals of the window.

Similarly, WNINCD is true whenever the input interval, from LEFT to RIGHT, is included in the input window, WIN---that is, whenever the interval lies entirely within one of the intervals of the window.

WNRELD is true whenever a specified relationship between the input windows, A and B, is satisfied. Each relationship corresponds to a ccomparison operator, OP. The complete set of operators recognized by WNRELD is shown below.

   '='          "is equal to (contains the same intervals as)"
   '<>'         "is not equal to"
   '<='         "is a subset of"
   '<'          "is a proper subset of"
   '>='         "is a superset of"
   '>'          "is a proper superset of"

For example, the expression

   WNRELD ( NEEDED, '<=', AVAIL )

is true whenever the window NEEDED is a subset of the window AVAIL. One window is a subset of another window if each of the intervals in the first window is included in one of the intervals in the second window. In addition, the first window is a proper subset of the second if the second window contains at least one point not contained in the first window. The following pairs of expressions are equivalent.

   WNRELD ( A, '>', B )
   WNRELD ( B, '<', A )
 
   WNRELD ( A, '>=', B )
   WNRELD ( B, '<=', A )

WNSUMD provides a summary of the input window, WIN. It computes the measure of the window (MEAS), and the average (AVG) and standard deviation (STDDEV) of the measures of the individual intervals in the window. It also returns the indices of the left endpoints of the shortest (SHORT) and longest (LONG) intervals in the window. All of these quantities and indices are zero if the window contains no intervals.

Top

Initialization Routines

WNVALD takes as input a double precision cell containing pairs of endpoints and validates it to form a window. The calling sequence is shown below.

   WNVALD ( SIZE, N, WIN )        { Validate }

On input, WIN is a cell of size SIZE containing N endpoints. During validation, the intervals are ordered, and overlapping intervals are merged. On output, the cardinality of WIN is the number of endpoints remaining, and the window is ready for use with any of the window routines.

Because validation is done in place, there is no chance of overflow. However, other errors may be detected. For example, if the left endpoint of any interval is greater than the corresponding right endpoint, WNVALD signals an error.

Validation is primarily useful for ordering and merging intervals added to a cell via APPNDD, read from input files or initialized via DATA statements.

Note that building a large window is done most efficiently by assigning the window elements and then calling WNVALD. Building up the window by repeated insertion requires repeated ordering operations; WNVALD does a single ordering operation.

Top

Summary

The following is a summary of the window routines in SPICELIB.

   Routine                               Functionality
   -------------------------------       -----------------------
   COM  ( LEFT, RIGHT, A, C )            Complement a window.
 
   CON  ( LEFT, RIGHT, WIN )             Contract intervals.
 
   DIF  ( A, B, C )                      Difference windows.
 
   ELM  ( POINT, WIN )                   Contains this point?
 
   EXP  ( LEFT, RIGHT, WIN )             Expand intervals.
 
   EXT  ( SIDE, WIN )                    Extract endpoints.
 
   FIL  ( SMALL, WIN )                   Fill small gaps.
 
   FLT  ( SMALL, WIN )                   Filter small intervals.
 
   INC  ( LEFT, RIGHT, WIN )             Includes this interval?
 
   INS  ( LEFT, RIGHT, WIN )             Insert an interval.
 
   INT  ( A, B, C )                      Intersect windows.
 
   REL  ( A, REL, B )                    Satisfies this relationship?
 
   SUM  ( WIN,
          MEAS,  AVG, STDDEV,
          SHORT, LONG         )          Summary of window.
 
 
   UNI  ( A, B, C )                      Union windows.
 
   VAL  ( SIZE, CARD, WIN )              Validate a window.

Table of Contents