IPP Software Navigation Tools IPP Links Communication Pan-STARRS Links

Changeset 361


Ignore:
Timestamp:
Mar 31, 2004, 10:54:37 PM (22 years ago)
Author:
Paul Price
Message:

Hacking linked lists, hashes, bit masks, and statistics.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/doc/pslib/psLibSDRS.tex

    r360 r361  
    1 %%% $Id: psLibSDRS.tex,v 1.22 2004-04-01 08:52:29 eugene Exp $
     1%%% $Id: psLibSDRS.tex,v 1.23 2004-04-01 08:54:37 price Exp $
    22\documentclass[panstarrs]{panstarrs}
    33
    … …  
    10061006the list, pointed to by both \code{psDlist.head} and
    10071007\code{psDlist.tail}.  If the data entry is \code{NULL}, then an empty
    1008 list, with both pointers set to \code{NULL} should be created. 
     1008list, with both pointers are set to \code{NULL} should be created.
    10091009
    10101010An entry may be added to the list with the function:
    … …  
    10161016\code{psDlist} may have changed.  The value of \code{where} specifies
    10171017if the specified data item should be placed on the front of the list
    1018 (\code{PS_DLIST_HEAD}), at the end of the list (\code{PS_DLIST_TAIL}),
    1019 \tbd{use of other options?}. 
     1018(\code{PS_DLIST_HEAD}), or at the end of the list
     1019(\code{PS_DLIST_TAIL}).
    10201020
    10211021A data item may be retrieved from the list with the function:
    … …  
    10261026of the special values: \code{PS_DLIST_HEAD}, \code{PS_DLIST_TAIL},
    10271027\code{PS_DLIST_PREV}, and \code{PS_DLIST_NEXT}, all of which are
    1028 defined as negative integers.
     1028defined as negative integers, allowing \code{where} to also be the
     1029index of one of the data items.
    10291030
    10301031A data item may be removed from the list with the function:
    … …  
    10371038\code{PS_DLIST_NEXT}, all of which are defined as negative integers.
    10381039If the value of \code{which} is \code{PS_DLIST_UNKNOWN}, then the data
    1039 item is identified by matching the pointer value with \code{void
    1040 *data}.
     1040item is identified by matching the pointer value with \code{void *data}.
    10411041
    10421042All data items placed onto lists (\code{psDlistAdd}) shall have their
    … …  
    11121112%
    11131113where \code{nbucket} is the number of buckets defined for the hash
    1114 functions, and \code{buckets} are the individual buckets, each of
    1115 which is defined by:
     1114functions, and \code{buckets} is an array of pointers to the
     1115individual buckets, each of which is defined by:
    11161116%
    11171117\begin{verbatim}
    … …  
    11241124where each bucket contains the value of the \code{key}, a pointer to
    11251125the \code{data}, and a pointer to the \code{next} list entry in the
    1126 bucket.
     1126bucket (in the event that two or more keys have the same hash value).
    11271127
    11281128A hash table is created with the following function:
    11291129\begin{verbatim}
    1130 psHash *psHashAlloc(int nbucket);
     1130psHash *psHashAlloc(void);
    11311131\end{verbatim}
    11321132which allocates the space for the hash table and initializes all of
    1133 the buckets.  \tbd{why specify nbucket? isn't it set by the hash
    1134 function?}. 
     1133the buckets.
    11351134
    11361135A data item may be added to the hash table with the function:
    … …  
    11441143same value of \code{key}.  The routine \code{psHashInsert} must
    11451144provide a non-NULL \code{itemFree} argument if it wishes to change the
    1146 value for previously inserted keys; if \code{itemFree} is NULL
     1145value for previously inserted keys; if \code{itemFree} is NULL,
    11471146attempting to insert a pre-existing key is an error, and the routine
    11481147will return NULL.  If \code{psHashInsert} succeeds it returns
    … …  
    11591158void *psHashRemove(psHash *table, char *key);
    11601159\end{verbatim}
    1161 \tbd{what is return value?}
     1160the return value of which is the value at the key that is removed (or
     1161NULL if no match is found).
    11621162
    11631163A complete hash table may be freed by calling:
    … …  
    11661166\end{verbatim}
    11671167where the function \code{itemFree} is provided to delete the
    1168 individual elements in the table.  If it is NULL this is the
    1169 responsibility of the caller.
     1168individual elements in the table.  If it is NULL it is the
     1169responsibility of the caller to free the elements.
    11701170
    11711171The function
    … …  
    11731173psDlist *psHashKeylist(psHast *table);
    11741174\end{verbatim}
    1175 returns the complete list of defined keys associated with the psHash
    1176 table as a linked list.
     1175returns the complete list of defined keys associated with the
     1176\code{psHash} table as a linked list.
    11771177
    11781178\section{Data manipulation}
    … …  
    12381238\end{verbatim}
    12391239
     1240\code{psBitMaskSet} sets the specified \code{bit} in the
     1241\code{psBitMask}, and returns the updated bitmask.  The input bitmask
     1242will be modified.
     1243
    12401244\begin{verbatim}
    12411245/** Check a bit mask.  Returns true or false */
    … …  
    12451249    );
    12461250\end{verbatim}
     1251
     1252\code{psBitMaskTest} returns a true value if the specified \code{bit}
     1253is set; otherwise, it returns a false value.
    12471254
    12481255\begin{verbatim}
    … …  
    12561263\end{verbatim}
    12571264
     1265\code{psBitMaskOp} returns the \code{psBitMask} that is the result of
     1266performing the specified \code{operator} (one of \code{"AND"},
     1267\code{"OR"}, or \code{"XOR"}) on \code{inMask1} and \code{inMask2}.
     1268
    12581269%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    12591270
    12601271\subsection{Sorting}
    12611272
    1262 We require the ability to sort an array of floating-point values:
     1273We require the ability to sort an array of floating-point values.  The
     1274following function returns the array, sorted from the smallest (i.e.\
     1275most negative) value in the first element, and the largest (i.e.\ most
     1276positive) value in the last element.  The input array, \code{myArray},
     1277may be sorted in-place if it is also specified as the \code{out}
     1278array.
    12631279
    12641280\begin{verbatim}
    … …  
    12701286\end{verbatim}
    12711287
    1272 We also require the ability to sort one array based on another.  In
    1273 order to facilitate this, we will have a sort function return an array
    1274 containing the induces for the unsorted list in the order appropriate
    1275 for the sorted array:
     1288We also require the ability to sort one array based on another.  For
     1289example, we may want to sort both \code{x} and \code{y} by the value
     1290in \code{x}.  In order to facilitate this, we will have a sort
     1291function return an array containing the indices for the unsorted list
     1292in the order appropriate for the sorted array:
    12761293
    12771294\begin{verbatim}
    … …  
    12811298            const psFloatArray *restrict myArray ///< Array to sort
    12821299    );
     1300\end{verbatim}
     1301
     1302Then the sorted arrays may be accessed in the following manner:
     1303
     1304\begin{verbatim}
     1305indexArray = psSortIndex(NULL, x);
     1306for (int i = 0; i < indexArray.n; i++) {
     1307    doMyFunc(x[indexArray[i]], y[indexArray[i]]);
     1308}
    12831309\end{verbatim}
    12841310
    … …  
    12951321\item Sample mean;
    12961322\item Sample median;
    1297 \item Sample mode;
    12981323\item Sample standard deviation;
    12991324\item Sample upper and lower quartiles;
    1300 \item Robust mean, associated error and number of values used to calculate;
    1301 \item Robust median, associated error and number of values used to calculate;
    1302 \item Robust mode, associated error and number of values used to calculate;
     1325\item Robust mean and number of values used to calculate;
     1326\item Robust median and number of values used to calculate;
     1327\item Robust mode and number of values used to calculate;
    13031328\item Robust standard deviation;
    13041329\item Robust upper and lower quartiles;
    1305 \item Clipped mean, associated error and number of values used to calculate;
     1330\item Clipped mean and number of values used to calculate;
    13061331\item Clipped standard deviation; and
    13071332\item Minimum and maximum value in array.
    … …  
    13251350             );
    13261351\end{verbatim}
     1352%
     1353This function takes the input data in \code{myArray} (with optional
     1354masking in \code{maskArray}, so that the user may explicitly reject
     1355specific entries) and a \code{psStats} structure, which will be
     1356altered and returned.
    13271357
    13281358The \code{psStats} structure is defined with entries for each of the
    … …  
    13321362/** generic statistics structure */
    13331363typedef struct {
    1334     double sampleMean;                  ///< formal mean of sample
    1335     double sampleMedian;                ///< formal median of sample
    1336     double sampleMode;                  ///< Formal mode of sample
    1337     double sampleStdev;                 ///< standard deviation of sample
    1338     double sampleUQ;                    ///< upper quartile of sample
    1339     double sampleLQ;                    ///< lower quartile of sample
    1340     double robustMean;                  ///< robust mean of array
    1341     double robustMeanError;             ///< error on robust mean
    1342     int    robustMeanNvalues;           ///< number of measurements used for robust mean
    1343     double robustMedian;                ///< robust median of array
    1344     double robustMedianError;           ///< error on robust median
    1345     int    robustMedianNvalues;         ///< number of measurements used for robust median
    1346     double robustMode;                  ///< Robust mode of array
    1347     double robustModeErr;               ///< Error in robust mode
    1348     int    robustModeNvalues;           ///< Number of measurements used for robust mode
    1349     double robustStdev;                 ///< robust standard deviation of array
    1350     double robustUQ;                    ///< robust upper quartile
    1351     double robustLQ;                    ///< robust lower quartile
    1352     double clippedMean;                 ///< Nsigma clipped mean
    1353     double clippedMeanError;            ///< error on clipped mean
    1354     int    clippedMeanNvalues;          ///< number of data points used for clipped mean
    1355     double clippedStdev;                ///< standard deviation after clipping
    1356     double clipSigma;                   ///< Nsigma used for clipping; user input
    1357     int    clipIter;                    ///< Number of clipping iterations; user input
    1358     double min;                         ///< minimum data value in array
    1359     double max;                         ///< maximum data value in array
    1360     int    nValues;                     ///< number of data values in array
    1361     psStatsOptions options;             ///< bitmask of calculated values
     1364    double sampleMean;                  ///< formal mean of sample
     1365    double sampleMedian;                ///< formal median of sample
     1366    double sampleStdev;                 ///< standard deviation of sample
     1367    double sampleUQ;                    ///< upper quartile of sample
     1368    double sampleLQ;                    ///< lower quartile of sample
     1369    double robustMean;                  ///< robust mean of array
     1370    int    robustMeanNvalues;           ///< number of measurements used for robust mean
     1371    double robustMedian;                ///< robust median of array
     1372    int    robustMedianNvalues;         ///< number of measurements used for robust median
     1373    double robustMode;                  ///< Robust mode of array
     1374    int    robustModeNvalues;           ///< Number of measurements used for robust mode
     1375    double robustStdev;                 ///< robust standard deviation of array
     1376    double robustUQ;                    ///< robust upper quartile
     1377    double robustLQ;                    ///< robust lower quartile
     1378    double clippedMean;                 ///< Nsigma clipped mean
     1379    int    clippedMeanNvalues;          ///< number of data points used for clipped mean
     1380    double clippedStdev;                ///< standard deviation after clipping
     1381    double clipSigma;                   ///< Nsigma used for clipping; user input
     1382    int    clipIter;                    ///< Number of clipping iterations; user input
     1383    double min;                         ///< minimum data value in array
     1384    double max;                         ///< maximum data value in array
     1385    int    nValues;                     ///< number of data values in array
     1386    psStatsOptions options;             ///< bitmask of calculated values
    13621387} psStats;
    13631388\end{verbatim}
     1389where \code{psStatsOptions} is defined with entries to turn on the
     1390calculation of each of the statistics:
     1391
     1392\begin{verbatim}
     1393/** statistics which may be calculated */
     1394typedef enum {
     1395    PS_STAT_SAMPLE_MEAN           = 0x000001,
     1396    PS_STAT_SAMPLE_MEDIAN         = 0x000002,
     1397    PS_STAT_SAMPLE_STDEV          = 0x000004,
     1398    PS_STAT_SAMPLE_UQ             = 0x000008,
     1399    PS_STAT_SAMPLE_LQ             = 0x000010,
     1400    PS_STAT_ROBUST_MEAN           = 0x000020,
     1401    PS_STAT_ROBUST_MEAN_NVALUES   = 0x000040,
     1402    PS_STAT_ROBUST_MEDIAN         = 0x000080,
     1403    PS_STAT_ROBUST_MEDIAN_NVALUES = 0x000100,
     1404    PS_STAT_ROBUST_MODE           = 0x000200,
     1405    PS_STAT_ROBUST_MODE_NVALUES   = 0x000400,
     1406    PS_STAT_ROBUST_STDEV          = 0x000800,
     1407    PS_STAT_ROBUST_UQ             = 0x001000,
     1408    PS_STAT_ROBUST_LQ             = 0x002000,
     1409    PS_STAT_CLIPPED_MEAN          = 0x004000,
     1410    PS_STAT_CLIPPED_MEAN_NVALUES  = 0x008000,
     1411    PS_STAT_CLIPPED_MEAN_NSIGMA   = 0x010000,
     1412    PS_STAT_CLIPPED_STDEV         = 0x020000,
     1413    PS_STAT_MAX                   = 0x040000,     
     1414    PS_STAT_MIN                   = 0x080000,
     1415    PS_STAT_NVALUES               = 0x100000
     1416} psStatsOptions;                         
     1417\end{verbatim}
     1418
     1419Associated constructors and destructors are also required:
     1420
     1421\begin{verbatim}
     1422/** Constructor */
     1423psStats *
     1424psStatsAlloc(psStatsOptions options     ///< Statistics to measure
     1425    );
     1426
     1427/** Destructor */
     1428void
     1429psStatsFree(psStats *restrict stats     ///< Stats structure to destroy
     1430    );
     1431\end{verbatim}
     1432
    13641433
    13651434\subsubsection{Histograms}
    13661435
    13671436We also require to be able to generate histograms, given a list of
    1368 upper and lower bounds for each of the bins, and maximum and minimum
    1369 values.
     1437upper and lower bounds for each of the bins.
    13701438
    13711439\begin{verbatim}
Note: See TracChangeset for help on using the changeset viewer.