/* isordv.f -- translated by f2c (version 19980913). You must link the resulting object file with the libraries: -lf2c -lm (in that order) */ #include "f2c.h" /* $Procedure ISORDV ( Is it an order vector ) */ logical isordv_(integer *array, integer *n) { /* System generated locals */ integer i__1, i__2; logical ret_val; /* Local variables */ integer i__, j; /* $ Abstract */ /* Determine whether an array of N items contains the integers */ /* 1 through N. */ /* $ Disclaimer */ /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */ /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */ /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */ /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */ /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */ /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */ /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */ /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */ /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */ /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */ /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */ /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */ /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */ /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */ /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */ /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */ /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */ /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */ /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */ /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */ /* $ Required_Reading */ /* None. */ /* $ Keywords */ /* SEARCH */ /* SORT */ /* UTILITY */ /* $ Declarations */ /* $ Brief_I/O */ /* Variable I/O Description */ /* -------- --- -------------------------------------------------- */ /* ARRAY I Array of integers. */ /* N I Number of integers in ARRAY. */ /* The function returns TRUE if the array contains the integers */ /* 1 through N, otherwise it returns FALSE. */ /* $ Detailed_Input */ /* ARRAY is an array of integers. Often this will be an array */ /* that is a candidate order vector to be passed to */ /* a routine for re-ordering some parallel array. */ /* N is the number of elements in ARRAY. */ /* $ Detailed_Output */ /* The function returns TRUE if the array contains the integers */ /* 1 through N. Otherwise it returns FALSE. */ /* $ Parameters */ /* None. */ /* $ Exceptions */ /* Error free. */ /* 1) If N < 1, the function returns .FALSE. */ /* $ Files */ /* None. */ /* $ Particulars */ /* This function provides a simple means of determining whether */ /* or not an array of N integers contains exactly the integers */ /* 1 through N. */ /* $ Examples */ /* 1) Suppose you wished to reorder an array of strings based upon */ /* a ranking array supplied by a user. If the ranking array */ /* contains any duplicates or refers to indices that are out */ /* of the range of valid indices for the array of strings, */ /* the attempt to reorder the array of strings cannot succeed. */ /* Its usually better to detect such a possibility before */ /* you begin trying to reorder the array of strings. This routine */ /* will detect the error. */ /* The block of code below illustrates this idea. */ /* IF ( ISORDV ( ORDVEC, N ) ) THEN */ /* ...reorder the input array of strings */ /* CALL REORDC ( ORDVEC, N, STRNGS ) */ /* ELSE */ /* ...state the problem and let the user decide what */ /* to do about it. */ /* . */ /* . */ /* . */ /* END IF */ /* 2) This routine can also be used to determine whether or not an */ /* array contains every integer between K and N (where K < N ). */ /* First subtract K-1 from each integer */ /* DO I = 1, N-K+1 */ /* ARRAY(I) = ARRAY(I) - K + 1 */ /* END DO */ /* See if the modified array is an order vector */ /* OK = ISORDV ( ARRAY, N-K ) */ /* Return the array to its original state. */ /* DO I = 1, N-K+1 */ /* ARRAY(I) = ARRAY(I) + K - 1 */ /* END DO */ /* $ Restrictions */ /* None. */ /* $ Literature_References */ /* None. */ /* $ Author_and_Institution */ /* N.J. Bachman (JPL) */ /* W.L. Taber (JPL) */ /* I.M. Underwood (JPL) */ /* $ Version */ /* - SPICELIB Version 1.0.1, 10-MAR-1992 (WLT) */ /* Comment section for permuted index source lines was added */ /* following the header. */ /* - SPICELIB Version 1.0.0, 6-MAR-1991 (NJB) (WLT) (IMU) */ /* -& */ /* $ Index_Entries */ /* test whether an integer array is an order vector */ /* -& */ /* Local variables */ /* Let's take care of the goofy case first. */ if (*n < 1) { ret_val = FALSE_; return ret_val; } else if (*n == 1) { ret_val = array[0] == 1; return ret_val; } /* Make an initial pass through the array to be sure we */ /* have legitimate values. */ i__1 = *n; for (i__ = 1; i__ <= i__1; ++i__) { if (array[i__ - 1] < 1 || array[i__ - 1] > *n) { ret_val = FALSE_; return ret_val; } } /* Ok. All of the values are in range. We just need to check */ /* that this array could actually be used as an order vector. */ /* For each I between 1 and N, ARRAY(I) is some integer between 1 */ /* and N. The only question remaining is whether the set */ /* { ARRAY(I), I=1,N } contains every integer between 1 and N. */ /* Suppose for a moment we could allocate a logical array called HITS */ /* LOGICAL HITS(N) */ /* Then the following scheme could be used to determine whether or */ /* not { ARRAY(I), I=1,N } contains every integer between 1 and N. */ /* Initialize every entry of HITS to .FALSE. */ /* DO I = 1, N */ /* HITS(I) = .FALSE. */ /* END DO */ /* Then for each I set HITS(ARRAY(I)) to .TRUE. */ /* DO I = 1, N */ /* HITS(ARRAY(I)) = .TRUE. */ /* END DO */ /* What can be said about HITS at this point? If for any entry J, */ /* HITS(J) is true then some ARRAY(I) is equal to J. */ /* If all HITS are .TRUE. then {ARRAY(I), I=1,N} is in fact the */ /* set of integers 1 to N. Otherwise those J such that */ /* HITS(J) = .FALSE. are the integers between 1 and N that are */ /* missed by ARRAY. */ /* It turns out we don't need to allocate an array of logicals; */ /* we can use just use part of the input array, ARRAY. */ /* The storage locations ARRAY(1) through ARRAY(N) can be viewed */ /* as two parallel arrays: SIGN_BIT and UNSIGNED */ /* SIGN */ /* BIT UNSIGNED PORTION */ /* +----+-----------------+ */ /* 1 | | | */ /* +----+-----------------+ */ /* 2 | | | */ /* +----+-----------------+ */ /* 3 | | | */ /* +----+-----------------+ */ /* . */ /* . */ /* . */ /* +----+-----------------+ */ /* N-1 | | | */ /* +----+-----------------+ */ /* N | | | */ /* +----+-----------------+ */ /* Since we know the value of all of the sign bits (it's '+') we can */ /* alter them and then reset them once we are done. */ /* We will choose for our array of HITS the SIGN_BITS of ARRAY. */ /* We regard '+' as FALSE and '-' as TRUE. */ /* DO I = 1, N */ /* SIGN_BIT ( UNSIGNED(I) ) = '-' */ /* END DO */ /* Then check to make sure that all of the sign bits are '-'. */ i__1 = *n; for (i__ = 1; i__ <= i__1; ++i__) { j = (i__2 = array[i__ - 1], abs(i__2)); array[j - 1] = -array[j - 1]; } /* Check each item to see if it's been hit. */ ret_val = TRUE_; i__1 = *n; for (i__ = 1; i__ <= i__1; ++i__) { ret_val = ret_val && array[i__ - 1] < 0; array[i__ - 1] = (i__2 = array[i__ - 1], abs(i__2)); } return ret_val; } /* isordv_ */