1 /*
2 * Revision Control Information
3 *
4 * $Source$
5 * $Author$
6 * $Revision$
7 * $Date$
8 *
9 */
10 //#include "port.h"
11 #include "sparse_int.h"
12
13 ABC_NAMESPACE_IMPL_START
14
15
16
17 /*
18 * allocate a new row vector
19 */
20 sm_row *
sm_row_alloc()21 sm_row_alloc()
22 {
23 register sm_row *prow;
24
25 #ifdef FAST_AND_LOOSE
26 if (sm_row_freelist == NIL(sm_row)) {
27 prow = ALLOC(sm_row, 1);
28 } else {
29 prow = sm_row_freelist;
30 sm_row_freelist = prow->next_row;
31 }
32 #else
33 prow = ALLOC(sm_row, 1);
34 #endif
35
36 prow->row_num = 0;
37 prow->length = 0;
38 prow->first_col = prow->last_col = NIL(sm_element);
39 prow->next_row = prow->prev_row = NIL(sm_row);
40 prow->flag = 0;
41 prow->user_word = NIL(char); /* for our user ... */
42 return prow;
43 }
44
45
46 /*
47 * free a row vector -- for FAST_AND_LOOSE, this is real cheap for rows;
48 * however, freeing a column must still walk down the column discarding
49 * the elements one-by-one; that is the only use for the extra '-DCOLS'
50 * compile flag ...
51 */
52 void
sm_row_free(prow)53 sm_row_free(prow)
54 register sm_row *prow;
55 {
56 #if defined(FAST_AND_LOOSE) && ! defined(COLS)
57 if (prow->first_col != NIL(sm_element)) {
58 /* Add the linked list of row items to the free list */
59 prow->last_col->next_col = sm_element_freelist;
60 sm_element_freelist = prow->first_col;
61 }
62
63 /* Add the row to the free list of rows */
64 prow->next_row = sm_row_freelist;
65 sm_row_freelist = prow;
66 #else
67 register sm_element *p, *pnext;
68
69 for(p = prow->first_col; p != 0; p = pnext) {
70 pnext = p->next_col;
71 sm_element_free(p);
72 }
73 FREE(prow);
74 #endif
75 }
76
77
78 /*
79 * duplicate an existing row
80 */
81 sm_row *
sm_row_dup(prow)82 sm_row_dup(prow)
83 register sm_row *prow;
84 {
85 register sm_row *pnew;
86 register sm_element *p;
87
88 pnew = sm_row_alloc();
89 for(p = prow->first_col; p != 0; p = p->next_col) {
90 (void) sm_row_insert(pnew, p->col_num);
91 }
92 return pnew;
93 }
94
95
96 /*
97 * insert an element into a row vector
98 */
99 sm_element *
sm_row_insert(prow,col)100 sm_row_insert(prow, col)
101 register sm_row *prow;
102 register int col;
103 {
104 register sm_element *test, *element;
105
106 /* get a new item, save its address */
107 sm_element_alloc(element);
108 test = element;
109 sorted_insert(sm_element, prow->first_col, prow->last_col, prow->length,
110 next_col, prev_col, col_num, col, test);
111
112 /* if item was not used, free it */
113 if (element != test) {
114 sm_element_free(element);
115 }
116
117 /* either way, return the current new value */
118 return test;
119 }
120
121
122 /*
123 * remove an element from a row vector
124 */
125 void
sm_row_remove(prow,col)126 sm_row_remove(prow, col)
127 register sm_row *prow;
128 register int col;
129 {
130 register sm_element *p;
131
132 for(p = prow->first_col; p != 0 && p->col_num < col; p = p->next_col)
133 ;
134 if (p != 0 && p->col_num == col) {
135 dll_unlink(p, prow->first_col, prow->last_col,
136 next_col, prev_col, prow->length);
137 sm_element_free(p);
138 }
139 }
140
141
142 /*
143 * find an element (if it is in the row vector)
144 */
145 sm_element *
sm_row_find(prow,col)146 sm_row_find(prow, col)
147 sm_row *prow;
148 int col;
149 {
150 register sm_element *p;
151
152 for(p = prow->first_col; p != 0 && p->col_num < col; p = p->next_col)
153 ;
154 if (p != 0 && p->col_num == col) {
155 return p;
156 } else {
157 return NIL(sm_element);
158 }
159 }
160
161 /*
162 * return 1 if row p2 contains row p1; 0 otherwise
163 */
164 int
sm_row_contains(p1,p2)165 sm_row_contains(p1, p2)
166 sm_row *p1, *p2;
167 {
168 register sm_element *q1, *q2;
169
170 q1 = p1->first_col;
171 q2 = p2->first_col;
172 while (q1 != 0) {
173 if (q2 == 0 || q1->col_num < q2->col_num) {
174 return 0;
175 } else if (q1->col_num == q2->col_num) {
176 q1 = q1->next_col;
177 q2 = q2->next_col;
178 } else {
179 q2 = q2->next_col;
180 }
181 }
182 return 1;
183 }
184
185
186 /*
187 * return 1 if row p1 and row p2 share an element in common
188 */
189 int
sm_row_intersects(p1,p2)190 sm_row_intersects(p1, p2)
191 sm_row *p1, *p2;
192 {
193 register sm_element *q1, *q2;
194
195 q1 = p1->first_col;
196 q2 = p2->first_col;
197 if (q1 == 0 || q2 == 0) return 0;
198 for(;;) {
199 if (q1->col_num < q2->col_num) {
200 if ((q1 = q1->next_col) == 0) {
201 return 0;
202 }
203 } else if (q1->col_num > q2->col_num) {
204 if ((q2 = q2->next_col) == 0) {
205 return 0;
206 }
207 } else {
208 return 1;
209 }
210 }
211 }
212
213
214 /*
215 * compare two rows, lexical ordering
216 */
217 int
sm_row_compare(p1,p2)218 sm_row_compare(p1, p2)
219 sm_row *p1, *p2;
220 {
221 register sm_element *q1, *q2;
222
223 q1 = p1->first_col;
224 q2 = p2->first_col;
225 while(q1 != 0 && q2 != 0) {
226 if (q1->col_num != q2->col_num) {
227 return q1->col_num - q2->col_num;
228 }
229 q1 = q1->next_col;
230 q2 = q2->next_col;
231 }
232
233 if (q1 != 0) {
234 return 1;
235 } else if (q2 != 0) {
236 return -1;
237 } else {
238 return 0;
239 }
240 }
241
242
243 /*
244 * return the intersection
245 */
246 sm_row *
sm_row_and(p1,p2)247 sm_row_and(p1, p2)
248 sm_row *p1, *p2;
249 {
250 register sm_element *q1, *q2;
251 register sm_row *result;
252
253 result = sm_row_alloc();
254 q1 = p1->first_col;
255 q2 = p2->first_col;
256 if (q1 == 0 || q2 == 0) return result;
257 for(;;) {
258 if (q1->col_num < q2->col_num) {
259 if ((q1 = q1->next_col) == 0) {
260 return result;
261 }
262 } else if (q1->col_num > q2->col_num) {
263 if ((q2 = q2->next_col) == 0) {
264 return result;
265 }
266 } else {
267 (void) sm_row_insert(result, q1->col_num);
268 if ((q1 = q1->next_col) == 0) {
269 return result;
270 }
271 if ((q2 = q2->next_col) == 0) {
272 return result;
273 }
274 }
275 }
276 }
277
278 int
sm_row_hash(prow,modulus)279 sm_row_hash(prow, modulus)
280 sm_row *prow;
281 int modulus;
282 {
283 register int sum;
284 register sm_element *p;
285
286 sum = 0;
287 for(p = prow->first_col; p != 0; p = p->next_col) {
288 sum = (sum*17 + p->col_num) % modulus;
289 }
290 return sum;
291 }
292
293 /*
294 * remove an element from a row vector (given a pointer to the element)
295 */
296 void
sm_row_remove_element(prow,p)297 sm_row_remove_element(prow, p)
298 register sm_row *prow;
299 register sm_element *p;
300 {
301 dll_unlink(p, prow->first_col, prow->last_col,
302 next_col, prev_col, prow->length);
303 sm_element_free(p);
304 }
305
306
307 void
sm_row_print(fp,prow)308 sm_row_print(fp, prow)
309 FILE *fp;
310 sm_row *prow;
311 {
312 sm_element *p;
313
314 for(p = prow->first_col; p != 0; p = p->next_col) {
315 (void) fprintf(fp, " %d", p->col_num);
316 }
317 }
318 ABC_NAMESPACE_IMPL_END
319
320