Index Page
Sets

Table of Contents 


   Sets
      Abstract
         Revisions
      Introduction
      Naming Conventions
      Initialization
      Cell functions
      Unary Functions
      Binary Functions
      Comparison Functions
      Summary
         Initialization
         Utilities
         Unary
         Binary
         Comparison
         Set Relationships


Top

Sets




Last revised on 2010 MAY 18 by B. V. Semenov.



Top

Abstract



Sets are SPICE data structures that are a special case of SPICE cells -- vectors of type double precision, integer, or character -- carrying with them their own dimension and knowledge of how many components have been used.



Top

Revisions



September 04, 2002

    Initial release for CSPICE.



Top

Introduction



The set data type is a subclass of the more basic CSPICE cell data type. In order to understand and use sets, you must first understand how to use cells.

A ``set'' is a character, integer, or double precision cell in which the following restrictions are observed:

    1. The elements of a set are distinct: sets never contain duplicate elements. Character sets are case sensitive. For example, a set may contain all of the following strings: 

            "AB", "Ab", "aB", "ab".
    2. The elements of a set are always stored contiguously in the set's data array.

    A numeric set's data occupy elements 

            [SPICE_CELL_CRTLSZ + 1] : [SPICE_CELL_CTRLSZ + n]
    of the sets's data array, where n is the cardinality of the set. The ith element is located at index 

            [SPICE_CELL_CRTLSZ + i]
    The parameter 

            SPICE_CELL_CTRLSZ
    is declared in the CSPICE header SpiceCel.h.

    In character sets, the ith string element starts at index 

            [SPICE_CELL_CRTLSZ + i]
    and the string ranges between the indices 

            [SPICE_CELL_CRTLSZ+i][0] : [SPICE_CELL_CRTLSZ+i][length-1]
    where length is cell member giving the string length associated with the set.

    3. The elements are sorted in increasing order. In character sets, the ordering of strings is Fortran-style: trailing blanks are not significant.

    4. In CSPICE sets, the cell member isSet has the value SPICETRUE.



Top

Naming Conventions



CSPICE contains several functions which allow sets to be manipulated. Type-dependent set functions come in groups of three, one for character sets, one for double precision sets, and one for integer sets. The name of each type-dependent set routine ends in c_c, d_c, or i_c, according to the type of set upon which it operates.

Thus, insrtc_c inserts an element into a character set, insrtd_c inserts an element into a double precision set, and insrti_c inserts an element into an integer set. We will refer to a class of type-dependent set routines by taking the name of any routine in the class and substituting an x for the last letter. Thus, the function elemx_c may refer to elemc_c, elemd_c, or elemi_c. In specific contexts, we will use the specific names of routines. A number of the CSPICE set functions are truly generic; these functions operate on a CSPICE set of any data type. The names of generic set functions have no final character designating data type. For example, the generic function union_c computes the union of two CSPICE sets of any data type.



Top

Initialization



As static variables, CSPICE sets (and all CSPICE cells) are automatically initialized effectively before program execution. The set attributes data type, maximum size, and if applicable, string length are provided when the set is declared via a CSPICE cell declaration macro. Unlike their SPICELIB counterparts, no run-time initialization calls are required to make a CSPICE set ready for use. Normally, an empty set can be filled with data via calls the set insertion function of the appropriate data type: 

   insrtc_c
   insrtd_c
   insrti_c
However, when working with large sets, it may be more efficient to construct the set by populating the set's data array and then sorting the array and removing duplicate items. After the set's data array has been populated, the function valid_c may be used to sort and prune the array: 

   valid_c ( size, n, &set );
Here size is the maximum allowed size of the set (normally the declared size of the data array) and n is the initial number of elements in the data array.

Efficient population of the set's data array may be done using the CSPICE cell ``append'' routines, the CSPICE cell element assignment macros, or the element reference macros. See the Cells Required Reading, cells.req, for further information. An even faster, but lower level, approach would be to use memmove, supplying the set's void pointer member ``data'' as a target address.



Top

Cell functions



A set is by definition a special kind of cell. Thus any of the general cell functions may be used with sets. Sets may be copied using copy_c, and the cardinality of a set may be determined by using card_c. The appndx_c functions may be used to add elements to a CSPICE set, provided the set is validated prior to use.

The CSPICE cell assignment, fetch, and element reference macros may be used to access data members of any CSPICE set. Note however that direct assignment of set elements may cause the set to become unordered or to contain duplicate items, in which case it cannot be used with the CSPICE set functions until it is validated.

An example of using the CSPICE cardinality function to define a loop bound (where we also use the character cell element reference macro to point to the cell's data members): 

   printf ( "Winners of the Nobel Prize for Physics:\n" );
 
   for ( i = 0;  i < card_c(nobel);  i++ )
   {
      printf ( "%s\n", SPICE_CELL_ELEM_C( nobel, i ) );
   }
The integer function size_c returns the size (maximum cardinality) of a set. This is useful primarily for predicting situations in which overflow can occur.



Top

Unary Functions



Unary functions operate on a single set. Two unary operations are supported, both of which may alter the contents of the input set.

    1. The insertion of an element into a set.

    2. The removal of an element from a set.

In the following example, the element 

   "PLUTO"
is removed from the character set `planets' and inserted into the character set `asteroids'. 

   removc_c ( "PLUTO", &planets   );
   insrtc_c ( "PLUTO", &asteroids );
If 

   "PLUTO"
is not an element of the set `planets', then the contents of `planets' are not changed. Similarly, if 

   "PLUTO"
is already an element of `asteroids', the contents of `asteroids' remain unchanged.

If a set is not large enough to accommodate the insertion of an element, the CSPICE error handling mechanism reports the excess.



Top

Binary Functions



Binary functions operate on two input sets to produce a third (distinct) output set. The four major algebraic binary set operations are supported: UNION, INTERSECTION, DIFFERENCE, and SYMMETRIC DIFFERENCE.

The UNION of two sets contains every element which is in the first set, or in the second set, or in both sets. 

   {a,b}        U       {c,d}       =    {a,b,c,d}
   {a,b,c}      U       {b,c,d}     =    {a,b,c,d}
   {a,b,c,d}    U       {}          =    {a,b,c,d}
   {}           U       {a,b,c,d}   =    {a,b,c,d}
   {}           U       {}          =    {}
The INTERSECTION of two sets contains every element which is in both the first set AND in the second set. 

   {a,b}        *       {c,d}       =    {}
   {a,b,c}      *       {b,c,d}     =    {b,c}
   {a,b,c,d}    *       {}          =    {}
   {}           *       {a,b,c,d}   =    {}
   {}           *       {}          =    {}
The DIFFERENCE of two sets contains every element which is in the first set, but NOT in the second. 

   {a,b}        -       {c,d}       =    {a,b}
   {a,b,c}      -       {b,c,d}     =    {a}
   {a,b,c,d}    -       {}          =    {a,b,c,d}
   {}           -       {a,b,c,d}   =    {}
   {}           -       {}          =    {}
The SYMMETRIC DIFFERENCE of two sets contains every element which is in the first set OR in the second set, but NOT in both sets. 

   {a,b}        ^       {c,d}       =    {a,b,c,d}
   {a,b,c}      ^       {b,c,d}     =    {a,d}
   {a,b,c,d}    ^       {}          =    {a,b,c,d}
   {}           ^       {a,b,c,d}   =    {a,b,c,d}
   {}           ^       {}          =    {}
Each of the functions takes two input sets and returns an output set.

In CSPICE, the functions carrying out these operations are type-independent.

The following calls 

   union_c ( &planets, &asteroids, &result );
   inter_c ( &planets, &asteroids, &result );
   diff_c  ( &planets, &asteroids, &result );
   sdiff_c ( &planets, &asteroids, &result );
respectively place the union, intersection, difference, and symmetric difference of the character sets `planets' and `asteroids' into the character set `result'.

In each case, if the output set `result' is not large enough to hold the result of the operation, as many elements as will fit are inserted into the set, and the CSPICE error handling mechanism reports the excess.

In each of the binary functions, the output set must be distinct from both of the input sets. (All four of the binary operations can be performed in place, but not efficiently. Consequently, for the sake of consistency, none of the functions work in place.) For example, the following calls are invalid. 

   union_c ( &current,  &new,      &current );
   inter_c ( &new,      &current,  &current );
In each of the examples above, the function may or may not return an error. However, the results will almost certainly be wrong.



Top

Comparison Functions



The comparison functions implement the following tests.

    1. Is a given item a member of a set?

    2. Does a given relationship exist between two sets?

In the first case, the SpiceBoolean functions_c elemc_c, elemd_c, and elemi_c are true whenever the specified item is an element of the specified set, and are false otherwise. Let the character sets `planets' and `asteroids' contain the following elements. 

   PLANETS            ASTEROIDS
   --------           ----------
   "Earth"            "Apollo"
   "Mars"             "Ceres"
   "Pluto"
   "Venus"
Then all of the following expressions are true. 

   elemc_c ( "Earth",  &planets   )
   elemc_c ( "Pluto",  &planets   )
   elemc_c ( "Ceres",  &asteroids )
And all of the following expressions are false. 

   elemc_c ( "Saturn", &planets   )
   elemc_c ( "Pluto",  &asteroids )
   elemc_c ( "CERES",  &asteroids )
The SpiceBoolean function set_c is true whenever the specified relationship between two sets exists, and is false otherwise.

In the following example, set_c is used to repeat an operation for as long as the integer set `finished' remains a proper subset of the integer set `planned'. 

   while ( set_c( &finished, "<", &planned )  )
   {
     . . .
   }
The full list of valid operators is given below. 

   Operator     is read
   --------     ---------------------------------------------
   "="          "is equal to (contains the same elements as)"
   "<>"         "is not equal to"
   "<="         "is a subset of"
   "<"          "is a proper subset of"
   ">="         "is a superset of"
   ">"          "is a proper superset of"
Let the integer sets `a', `b', and `c' contain the following elements. Let `e' be an empty integer set. 

   a        b        c
   ---      ---      ---
   1        1        1
   2        3        3
   3
   4
Then all of the following expressions are true. 

   set_c ( &b, "=",  &c )      "b is equal to c"
   set_c ( &a, "<>", &c )      "a is not equal to c"
   set_c ( &a, ">",  &b )      "a is a proper superset of b"
   set_c ( &b, "<=", &c )      "b is a subset of c"
   set_c ( &c, "<=", &b )      "c is a subset of b"
   set_c ( &a, "<=", &a )      "a is a subset of a"
   set_c ( &e, "<=", &b )      "e is a subset of b"
   set_c ( &e, "<",  &b )      "e is a proper subset of b"
   set_c ( &e, "<=", &e )      "e is a subset of e"
And all of the following are false. 

   set_c ( &b, "<>",  &c )     "b is not equal to c"
   set_c ( &a, "=",   &c )     "a is equal to c"
   set_c ( &a, "<",   &b )     "a is a proper subset of b"
   set_c ( &b, "<",   &c )     "b is a proper subset of c"
   set_c ( &b, ">=",  &a )     "b is a superset of a"
   set_c ( &a, ">",   &a )     "a is a proper superset of a"
   set_c ( &e, ">=",  &a )     "e is a superset of a"
   set_c ( &e, "<",   &e )     "e is a proper subset of e"


Top

Summary



The following table summarizes the set routines in the CSPICE library.



Top

Initialization



valid_c ( size, n, set )

Validate a set from a CSPICE cell of any data type.


Top

Utilities



size_c ( cell )

Return the size of a cell of any data type
card_c ( cell )

Return the cardinality of a cell of any data type.
copy_c ( orig, copy )

Copy the contents of a cell.


Top

Unary



insrtx_c ( item, set )

Insert an item into a set.
removx_c ( item, set )

Remove an item from a set.


Top

Binary



union_c ( a, b, c )

Take the union of two sets of any data type.
inter_c ( a, b, c )

Take the intersection of two sets of any data type.
diff_c ( a, b, c )

Take the difference of two sets of any data type.
sdiff_c ( a, b, c )

Take the symmetric difference of two sets of any data type.


Top

Comparison



elemx_c ( item, set )

Is an item in a set?
set_c ( a, rel, b )

What is the relationship between two sets? Set relationships are listed below.


Top

Set Relationships 



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