| #include "port.h" |
| #include "sparse_int.h" |
| |
| |
| /* |
| * allocate a new row vector |
| */ |
| sm_row * |
| sm_row_alloc() |
| { |
| register sm_row *prow; |
| |
| #ifdef FAST_AND_LOOSE |
| if (sm_row_freelist == NIL(sm_row)) { |
| prow = ALLOC(sm_row, 1); |
| } else { |
| prow = sm_row_freelist; |
| sm_row_freelist = prow->next_row; |
| } |
| #else |
| prow = ALLOC(sm_row, 1); |
| #endif |
| |
| prow->row_num = 0; |
| prow->length = 0; |
| prow->first_col = prow->last_col = NIL(sm_element); |
| prow->next_row = prow->prev_row = NIL(sm_row); |
| prow->flag = 0; |
| prow->user_word = NIL(char); /* for our user ... */ |
| return prow; |
| } |
| |
| |
| /* |
| * free a row vector -- for FAST_AND_LOOSE, this is real cheap for rows; |
| * however, freeing a column must still walk down the column discarding |
| * the elements one-by-one; that is the only use for the extra '-DCOLS' |
| * compile flag ... |
| */ |
| void |
| sm_row_free(prow) |
| register sm_row *prow; |
| { |
| #if defined(FAST_AND_LOOSE) && ! defined(COLS) |
| if (prow->first_col != NIL(sm_element)) { |
| /* Add the linked list of row items to the free list */ |
| prow->last_col->next_col = sm_element_freelist; |
| sm_element_freelist = prow->first_col; |
| } |
| |
| /* Add the row to the free list of rows */ |
| prow->next_row = sm_row_freelist; |
| sm_row_freelist = prow; |
| #else |
| register sm_element *p, *pnext; |
| |
| for(p = prow->first_col; p != 0; p = pnext) { |
| pnext = p->next_col; |
| sm_element_free(p); |
| } |
| FREE(prow); |
| #endif |
| } |
| |
| |
| /* |
| * duplicate an existing row |
| */ |
| sm_row * |
| sm_row_dup(prow) |
| register sm_row *prow; |
| { |
| register sm_row *pnew; |
| register sm_element *p; |
| |
| pnew = sm_row_alloc(); |
| for(p = prow->first_col; p != 0; p = p->next_col) { |
| (void) sm_row_insert(pnew, p->col_num); |
| } |
| return pnew; |
| } |
| |
| |
| /* |
| * insert an element into a row vector |
| */ |
| sm_element * |
| sm_row_insert(prow, col) |
| register sm_row *prow; |
| register int col; |
| { |
| register sm_element *test, *element; |
| |
| /* get a new item, save its address */ |
| sm_element_alloc(element); |
| test = element; |
| sorted_insert(sm_element, prow->first_col, prow->last_col, prow->length, |
| next_col, prev_col, col_num, col, test); |
| |
| /* if item was not used, free it */ |
| if (element != test) { |
| sm_element_free(element); |
| } |
| |
| /* either way, return the current new value */ |
| return test; |
| } |
| |
| |
| /* |
| * remove an element from a row vector |
| */ |
| void |
| sm_row_remove(prow, col) |
| register sm_row *prow; |
| register int col; |
| { |
| register sm_element *p; |
| |
| for(p = prow->first_col; p != 0 && p->col_num < col; p = p->next_col) |
| ; |
| if (p != 0 && p->col_num == col) { |
| dll_unlink(p, prow->first_col, prow->last_col, |
| next_col, prev_col, prow->length); |
| sm_element_free(p); |
| } |
| } |
| |
| |
| /* |
| * find an element (if it is in the row vector) |
| */ |
| sm_element * |
| sm_row_find(prow, col) |
| sm_row *prow; |
| int col; |
| { |
| register sm_element *p; |
| |
| for(p = prow->first_col; p != 0 && p->col_num < col; p = p->next_col) |
| ; |
| if (p != 0 && p->col_num == col) { |
| return p; |
| } else { |
| return NIL(sm_element); |
| } |
| } |
| |
| /* |
| * return 1 if row p2 contains row p1; 0 otherwise |
| */ |
| int |
| sm_row_contains(p1, p2) |
| sm_row *p1, *p2; |
| { |
| register sm_element *q1, *q2; |
| |
| q1 = p1->first_col; |
| q2 = p2->first_col; |
| while (q1 != 0) { |
| if (q2 == 0 || q1->col_num < q2->col_num) { |
| return 0; |
| } else if (q1->col_num == q2->col_num) { |
| q1 = q1->next_col; |
| q2 = q2->next_col; |
| } else { |
| q2 = q2->next_col; |
| } |
| } |
| return 1; |
| } |
| |
| |
| /* |
| * return 1 if row p1 and row p2 share an element in common |
| */ |
| int |
| sm_row_intersects(p1, p2) |
| sm_row *p1, *p2; |
| { |
| register sm_element *q1, *q2; |
| |
| q1 = p1->first_col; |
| q2 = p2->first_col; |
| if (q1 == 0 || q2 == 0) return 0; |
| for(;;) { |
| if (q1->col_num < q2->col_num) { |
| if ((q1 = q1->next_col) == 0) { |
| return 0; |
| } |
| } else if (q1->col_num > q2->col_num) { |
| if ((q2 = q2->next_col) == 0) { |
| return 0; |
| } |
| } else { |
| return 1; |
| } |
| } |
| } |
| |
| |
| /* |
| * compare two rows, lexical ordering |
| */ |
| int |
| sm_row_compare(p1, p2) |
| sm_row *p1, *p2; |
| { |
| register sm_element *q1, *q2; |
| |
| q1 = p1->first_col; |
| q2 = p2->first_col; |
| while(q1 != 0 && q2 != 0) { |
| if (q1->col_num != q2->col_num) { |
| return q1->col_num - q2->col_num; |
| } |
| q1 = q1->next_col; |
| q2 = q2->next_col; |
| } |
| |
| if (q1 != 0) { |
| return 1; |
| } else if (q2 != 0) { |
| return -1; |
| } else { |
| return 0; |
| } |
| } |
| |
| |
| /* |
| * return the intersection |
| */ |
| sm_row * |
| sm_row_and(p1, p2) |
| sm_row *p1, *p2; |
| { |
| register sm_element *q1, *q2; |
| register sm_row *result; |
| |
| result = sm_row_alloc(); |
| q1 = p1->first_col; |
| q2 = p2->first_col; |
| if (q1 == 0 || q2 == 0) return result; |
| for(;;) { |
| if (q1->col_num < q2->col_num) { |
| if ((q1 = q1->next_col) == 0) { |
| return result; |
| } |
| } else if (q1->col_num > q2->col_num) { |
| if ((q2 = q2->next_col) == 0) { |
| return result; |
| } |
| } else { |
| (void) sm_row_insert(result, q1->col_num); |
| if ((q1 = q1->next_col) == 0) { |
| return result; |
| } |
| if ((q2 = q2->next_col) == 0) { |
| return result; |
| } |
| } |
| } |
| } |
| |
| int |
| sm_row_hash(prow, modulus) |
| sm_row *prow; |
| int modulus; |
| { |
| register int sum; |
| register sm_element *p; |
| |
| sum = 0; |
| for(p = prow->first_col; p != 0; p = p->next_col) { |
| sum = (sum*17 + p->col_num) % modulus; |
| } |
| return sum; |
| } |
| |
| /* |
| * remove an element from a row vector (given a pointer to the element) |
| */ |
| void |
| sm_row_remove_element(prow, p) |
| register sm_row *prow; |
| register sm_element *p; |
| { |
| dll_unlink(p, prow->first_col, prow->last_col, |
| next_col, prev_col, prow->length); |
| sm_element_free(p); |
| } |
| |
| |
| void |
| sm_row_print(fp, prow) |
| FILE *fp; |
| sm_row *prow; |
| { |
| sm_element *p; |
| |
| for(p = prow->first_col; p != 0; p = p->next_col) { |
| (void) fprintf(fp, " %d", p->col_num); |
| } |
| } |