1 /* zzuntngl.f -- translated by f2c (version 19980913).
2 You must link the resulting object file with the libraries:
3 -lf2c -lm (in that order)
4 */
5
6 #include "f2c.h"
7
8 /* $Procedure ZZUNTNGL ( Untangle an AB linked-cell list ) */
zzuntngl_(integer * nptr,integer * maxcel,integer * cells,integer * maxb,integer * pntrs,integer * nout,integer * outlst)9 /* Subroutine */ int zzuntngl_(integer *nptr, integer *maxcel, integer *cells,
10 integer *maxb, integer *pntrs, integer *nout, integer *outlst)
11 {
12 /* System generated locals */
13 integer i__1, i__2;
14
15 /* Local variables */
16 integer aval, room;
17 extern /* Subroutine */ int zztrvlnk_(integer *, integer *, integer *,
18 integer *, integer *, integer *, integer *, integer *), chkin_(
19 char *, ftnlen);
20 extern logical failed_(void);
21 integer nfound;
22 extern /* Subroutine */ int sigerr_(char *, ftnlen), chkout_(char *,
23 ftnlen), setmsg_(char *, ftnlen), errint_(char *, integer *,
24 ftnlen);
25 integer ptrdex;
26 extern logical return_(void);
27
28 /* $ Abstract */
29
30 /* Untangle an unsorted AB linked-cell list into an A-index and */
31 /* associated B-list. */
32
33 /* $ Disclaimer */
34
35 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
36 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
37 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
38 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
39 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
40 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
41 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
42 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
43 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
44 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
45
46 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
47 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
48 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
49 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
50 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
51 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
52
53 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
54 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
55 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
56 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
57
58 /* $ Required_Reading */
59
60 /* None. */
61
62 /* $ Keywords */
63
64 /* AB linked list */
65
66 /* $ Declarations */
67 /* $ Brief_I/O */
68
69 /* VARIABLE I/O DESCRIPTION */
70 /* -------- --- -------------------------------------------------- */
71 /* NPTR I Length of A-list. */
72 /* MAXCEL I Size of cell list. */
73 /* CELLS I AB cell linked list. */
74 /* MAXB I Maximum allowed dimension of B list. */
75 /* PNTRS I-O Pointer array. */
76 /* NOUT O Length of B-list. */
77 /* OUTLST O B-list. */
78
79 /* $ Detailed_Input */
80
81 /* NPTR is the size of the input pointer array INPTR. */
82
83 /* MAXCEL is the number of cells in the CELLS array. That */
84 /* array has dimensions */
85
86 /* (2, MAXCEL) */
87
88 /* CELLS is an array containing linked lists of "B" values. */
89 /* The elements at indices */
90
91 /* (1,K) */
92 /* (2,K) */
93
94 /* are, respectively, a "B" value and a pointer to */
95 /* another element of the array. Null pointers are */
96 /* indicated by the value -1. */
97
98 /* Each linked list in CELLS contains a set of "B" */
99 /* values associated with a particular "A" value. */
100 /* The input pointer list maps "A" values to the head */
101 /* of the associated list in CELLS. */
102
103 /* MAXB is the maximum number of elements in the output */
104 /* array OUTLST. */
105
106 /* PNTRS is an array of pointers from A values to */
107 /* linked lists of "B" entries in the CELLS array. */
108
109 /* $ Detailed_Output */
110
111 /* PNTRS is an array of pointers that map "A" values to */
112 /* their associated "B" values in the array OUTLST. */
113 /* Null pointers are indicated by the value -1. */
114
115 /* PNTRS must be declared with size at least NPTR. */
116
117 /* NOUT is the number of elements in the output list OUTLST. */
118
119 /* OUTLST is an array containing lists of "B" values. The Kth */
120 /* element of PNTRS is the index of the start of a list */
121 /* in OUTLST of "B" values associated with the "A" value */
122 /* having index K. The list of values associated with an */
123 /* "A" value starts with a count and is followed by */
124 /* the values themselves. */
125
126 /* $ Parameters */
127
128 /* None. */
129
130 /* $ Exceptions */
131
132 /* 1) The routine signals the error SPICE(BARRAYTOOSMALL) if the */
133 /* entire set of B-value lists from the input cell array, */
134 /* including the counts for each list, array cannot be stored in */
135 /* the OUTLST array. */
136
137 /* $ Files */
138
139 /* None. */
140
141 /* $ Particulars */
142
143 /* The AB list routines support manipulation of a data structure that */
144 /* represents a one-to-many mapping from a set A to a set B. Each */
145 /* element of set A is mapped to a set of values from B, where the */
146 /* range values are represented by a linked list of entries in the */
147 /* cell array. */
148
149 /* The elements of set B associated with the Ith element of A are */
150 /* stored in a linked list of cells starting with the cell */
151 /* consisting of elements */
152
153 /* CELLS(*,PNTRS(I)) */
154
155 /* The set A is really an abstraction: it's just some finite set */
156 /* with size in the range 1:MAXA. The input AVAL is not a member of */
157 /* A but rather just an index into A. For consistency with existing */
158 /* code, the name AVAL has been retained. */
159
160 /* The fact that B values are stored in linked lists enables a */
161 /* program to store entries for A-B associations in random order. */
162 /* For example, in the process of constructing DSK type 2 segments, */
163 /* the of non-empty fine voxels intersected by a given plate can be */
164 /* computed; then an entry representing a voxel-plate association */
165 /* can be made for each fine voxel in the set. In this case, the */
166 /* set "A" is the set of fine voxels belonging to non-empty coarse */
167 /* voxels. */
168
169 /* This routine supports creation of DSK type 2 segments. It is used */
170 /* for creation of both voxel-plate association data structures and */
171 /* of vertex-plate association data structures. */
172
173 /* $ Examples */
174
175 /* See usage in ZZMKSPIN. */
176
177 /* $ Restrictions */
178
179 /* None. */
180
181 /* $ Literature_References */
182
183 /* None. */
184
185 /* $ Author_and_Institution */
186
187 /* N.J. Bachman (JPL) */
188 /* J.A. Bytof (JPL) */
189
190 /* $ Version */
191
192 /* - SPICELIB Version 1.0.0, 23-AUG-2016 (NJB) */
193
194 /* 07-JAN-2016 (NJB) */
195
196 /* Argument list change: removed INPTR; renamed */
197 /* OUTPTR to PNTRS. PNTRS is an in-out argument. */
198 /* Updated header. */
199
200 /* 30-APR-2014 (NJB) */
201
202 /* Changed argument list to accommodate */
203 /* better error checking. Added error checks */
204 /* for array overflows. Changed calls to */
205 /* ADDLNK and TRVLNK. Updated header I/O */
206 /* descriptions. */
207
208 /* 08-OCT-2009 (NJB) */
209
210 /* Re-ordered header sections. */
211
212 /* 16-JUL-2004 (EDW) */
213
214 /* Added check on NPTR to ensure it's smaller */
215 /* than the size of the pointer arrays. */
216
217 /* Removed use of BVAL array, TRVLNK now directly */
218 /* writes to OUTLST array. */
219
220 /* 03-FEB-1999 (JAB) */
221
222
223 /* -& */
224 /* $ Index_Entries */
225
226 /* AB linked list */
227
228 /* -& */
229
230 /* SPICELIB functions */
231
232
233 /* Local Variables */
234
235
236 /* Standard SPICE error handling. */
237
238 if (return_()) {
239 return 0;
240 }
241 chkin_("ZZUNTNGL", (ftnlen)8);
242 if (*nptr > *maxcel) {
243 setmsg_("Input pointer array is larger than cell array. Pointer arra"
244 "y size = #1. Cell array size = #2.", (ftnlen)93);
245 errint_("#1", nptr, (ftnlen)2);
246 errint_("#2", maxcel, (ftnlen)2);
247 sigerr_("SPICE(BARRAYTOOSMALL)", (ftnlen)21);
248 chkout_("ZZUNTNGL", (ftnlen)8);
249 return 0;
250 }
251
252 /* ROOM is the remaining room in the output list. */
253
254 room = *maxb;
255
256 /* Initialize pointer index. */
257
258 ptrdex = 0;
259
260 /* Loop over all A-values. */
261
262 i__1 = *nptr;
263 for (aval = 1; aval <= i__1; ++aval) {
264
265 /* Traverse the chained list for a particular A-value */
266 /* and collect associated B-values. If B-values exists, */
267 /* return the number of B-vals to the OUTLST array */
268 /* at element PTRDEX + 1; return the list of B-vals */
269 /* starting at element PTRDEX + 2. */
270
271 /* Make sure the output pointers below are in range. */
272
273 if (ptrdex + 2 > *maxb) {
274 setmsg_("Index larger than output array. Index = #1. Array size "
275 "= #2.", (ftnlen)60);
276 i__2 = ptrdex + 2;
277 errint_("#1", &i__2, (ftnlen)2);
278 errint_("#2", maxb, (ftnlen)2);
279 sigerr_("SPICE(BARRAYTOOSMALL)", (ftnlen)21);
280 chkout_("ZZUNTNGL", (ftnlen)8);
281 return 0;
282 }
283 if (room <= 0) {
284 setmsg_("Remaining room in output array is #1. Current input poi"
285 "nter index = #2. Output array size = #3. Output pointer "
286 "index is #4.", (ftnlen)123);
287 errint_("#1", &room, (ftnlen)2);
288 errint_("#2", &aval, (ftnlen)2);
289 errint_("#3", maxb, (ftnlen)2);
290 errint_("#4", &ptrdex, (ftnlen)2);
291 sigerr_("SPICE(BARRAYTOOSMALL)", (ftnlen)21);
292 chkout_("ZZUNTNGL", (ftnlen)8);
293 return 0;
294 }
295 zztrvlnk_(&aval, nptr, pntrs, maxcel, cells, &room, &outlst[ptrdex], &
296 outlst[ptrdex + 1]);
297 if (failed_()) {
298 chkout_("ZZUNTNGL", (ftnlen)8);
299 return 0;
300 }
301
302 /* Increment pointer PTRDEX if we found any B-vals. */
303
304 nfound = outlst[ptrdex];
305 if (nfound > 0) {
306
307 /* Store in PNTRS the pointer to the returned list. */
308 /* This assignment overwrites the input pointer from */
309 /* AVAL to the head of the associated list in CELLS. */
310
311 pntrs[aval - 1] = ptrdex + 1;
312
313 /* Update the count of available spaces in the */
314 /* output list. Account for the list size stored */
315 /* at the front of the list. */
316
317 room -= nfound + 1;
318
319 /* Increment PTRDEX to mark the position of the final */
320 /* B-val. */
321
322 ptrdex = ptrdex + 1 + nfound;
323 } else {
324
325 /* If no associated B-values exist, set the */
326 /* PNTRS element to -1, indicating no B-value. */
327
328 pntrs[aval - 1] = -1;
329 }
330 }
331
332 /* Return the current pointer value. */
333
334 *nout = ptrdex;
335
336 /* Standard SPICE error handling. */
337
338 chkout_("ZZUNTNGL", (ftnlen)8);
339 return 0;
340 } /* zzuntngl_ */
341
342