source: vis_dev/glu-2.3/src/sparse/rows.c @ 43

Last change on this file since 43 was 13, checked in by cecile, 13 years ago

library glu 2.3

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