| #include "port.h" |
| #include "sparse_int.h" |
| |
| |
| /* |
| * allocate a new col vector |
| */ |
| sm_col * |
| sm_col_alloc() |
| { |
| register sm_col *pcol; |
| |
| #ifdef FAST_AND_LOOSE |
| if (sm_col_freelist == NIL(sm_col)) { |
| pcol = ALLOC(sm_col, 1); |
| } else { |
| pcol = sm_col_freelist; |
| sm_col_freelist = pcol->next_col; |
| } |
| #else |
| pcol = ALLOC(sm_col, 1); |
| #endif |
| |
| pcol->col_num = 0; |
| pcol->length = 0; |
| pcol->first_row = pcol->last_row = NIL(sm_element); |
| pcol->next_col = pcol->prev_col = NIL(sm_col); |
| pcol->flag = 0; |
| pcol->user_word = NIL(char); /* for our user ... */ |
| return pcol; |
| } |
| |
| |
| /* |
| * free a col vector -- for FAST_AND_LOOSE, this is real cheap for cols; |
| * however, freeing a rowumn must still walk down the rowumn discarding |
| * the elements one-by-one; that is the only use for the extra '-DCOLS' |
| * compile flag ... |
| */ |
| void |
| sm_col_free(pcol) |
| register sm_col *pcol; |
| { |
| #if defined(FAST_AND_LOOSE) && ! defined(COLS) |
| if (pcol->first_row != NIL(sm_element)) { |
| /* Add the linked list of col items to the free list */ |
| pcol->last_row->next_row = sm_element_freelist; |
| sm_element_freelist = pcol->first_row; |
| } |
| |
| /* Add the col to the free list of cols */ |
| pcol->next_col = sm_col_freelist; |
| sm_col_freelist = pcol; |
| #else |
| register sm_element *p, *pnext; |
| |
| for(p = pcol->first_row; p != 0; p = pnext) { |
| pnext = p->next_row; |
| sm_element_free(p); |
| } |
| FREE(pcol); |
| #endif |
| } |
| |
| |
| /* |
| * duplicate an existing col |
| */ |
| sm_col * |
| sm_col_dup(pcol) |
| register sm_col *pcol; |
| { |
| register sm_col *pnew; |
| register sm_element *p; |
| |
| pnew = sm_col_alloc(); |
| for(p = pcol->first_row; p != 0; p = p->next_row) { |
| (void) sm_col_insert(pnew, p->row_num); |
| } |
| return pnew; |
| } |
| |
| |
| /* |
| * insert an element into a col vector |
| */ |
| sm_element * |
| sm_col_insert(pcol, row) |
| register sm_col *pcol; |
| register int row; |
| { |
| register sm_element *test, *element; |
| |
| /* get a new item, save its address */ |
| sm_element_alloc(element); |
| test = element; |
| sorted_insert(sm_element, pcol->first_row, pcol->last_row, pcol->length, |
| next_row, prev_row, row_num, row, 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 col vector |
| */ |
| void |
| sm_col_remove(pcol, row) |
| register sm_col *pcol; |
| register int row; |
| { |
| register sm_element *p; |
| |
| for(p = pcol->first_row; p != 0 && p->row_num < row; p = p->next_row) |
| ; |
| if (p != 0 && p->row_num == row) { |
| dll_unlink(p, pcol->first_row, pcol->last_row, |
| next_row, prev_row, pcol->length); |
| sm_element_free(p); |
| } |
| } |
| |
| |
| /* |
| * find an element (if it is in the col vector) |
| */ |
| sm_element * |
| sm_col_find(pcol, row) |
| sm_col *pcol; |
| int row; |
| { |
| register sm_element *p; |
| |
| for(p = pcol->first_row; p != 0 && p->row_num < row; p = p->next_row) |
| ; |
| if (p != 0 && p->row_num == row) { |
| return p; |
| } else { |
| return NIL(sm_element); |
| } |
| } |
| |
| /* |
| * return 1 if col p2 contains col p1; 0 otherwise |
| */ |
| int |
| sm_col_contains(p1, p2) |
| sm_col *p1, *p2; |
| { |
| register sm_element *q1, *q2; |
| |
| q1 = p1->first_row; |
| q2 = p2->first_row; |
| while (q1 != 0) { |
| if (q2 == 0 || q1->row_num < q2->row_num) { |
| return 0; |
| } else if (q1->row_num == q2->row_num) { |
| q1 = q1->next_row; |
| q2 = q2->next_row; |
| } else { |
| q2 = q2->next_row; |
| } |
| } |
| return 1; |
| } |
| |
| |
| /* |
| * return 1 if col p1 and col p2 share an element in common |
| */ |
| int |
| sm_col_intersects(p1, p2) |
| sm_col *p1, *p2; |
| { |
| register sm_element *q1, *q2; |
| |
| q1 = p1->first_row; |
| q2 = p2->first_row; |
| if (q1 == 0 || q2 == 0) return 0; |
| for(;;) { |
| if (q1->row_num < q2->row_num) { |
| if ((q1 = q1->next_row) == 0) { |
| return 0; |
| } |
| } else if (q1->row_num > q2->row_num) { |
| if ((q2 = q2->next_row) == 0) { |
| return 0; |
| } |
| } else { |
| return 1; |
| } |
| } |
| } |
| |
| |
| /* |
| * compare two cols, lexical ordering |
| */ |
| int |
| sm_col_compare(p1, p2) |
| sm_col *p1, *p2; |
| { |
| register sm_element *q1, *q2; |
| |
| q1 = p1->first_row; |
| q2 = p2->first_row; |
| while(q1 != 0 && q2 != 0) { |
| if (q1->row_num != q2->row_num) { |
| return q1->row_num - q2->row_num; |
| } |
| q1 = q1->next_row; |
| q2 = q2->next_row; |
| } |
| |
| if (q1 != 0) { |
| return 1; |
| } else if (q2 != 0) { |
| return -1; |
| } else { |
| return 0; |
| } |
| } |
| |
| |
| /* |
| * return the intersection |
| */ |
| sm_col * |
| sm_col_and(p1, p2) |
| sm_col *p1, *p2; |
| { |
| register sm_element *q1, *q2; |
| register sm_col *result; |
| |
| result = sm_col_alloc(); |
| q1 = p1->first_row; |
| q2 = p2->first_row; |
| if (q1 == 0 || q2 == 0) return result; |
| for(;;) { |
| if (q1->row_num < q2->row_num) { |
| if ((q1 = q1->next_row) == 0) { |
| return result; |
| } |
| } else if (q1->row_num > q2->row_num) { |
| if ((q2 = q2->next_row) == 0) { |
| return result; |
| } |
| } else { |
| (void) sm_col_insert(result, q1->row_num); |
| if ((q1 = q1->next_row) == 0) { |
| return result; |
| } |
| if ((q2 = q2->next_row) == 0) { |
| return result; |
| } |
| } |
| } |
| } |
| |
| int |
| sm_col_hash(pcol, modulus) |
| sm_col *pcol; |
| int modulus; |
| { |
| register int sum; |
| register sm_element *p; |
| |
| sum = 0; |
| for(p = pcol->first_row; p != 0; p = p->next_row) { |
| sum = (sum*17 + p->row_num) % modulus; |
| } |
| return sum; |
| } |
| |
| /* |
| * remove an element from a col vector (given a pointer to the element) |
| */ |
| void |
| sm_col_remove_element(pcol, p) |
| register sm_col *pcol; |
| register sm_element *p; |
| { |
| dll_unlink(p, pcol->first_row, pcol->last_row, |
| next_row, prev_row, pcol->length); |
| sm_element_free(p); |
| } |
| |
| |
| void |
| sm_col_print(fp, pcol) |
| FILE *fp; |
| sm_col *pcol; |
| { |
| sm_element *p; |
| |
| for(p = pcol->first_row; p != 0; p = p->next_row) { |
| (void) fprintf(fp, " %d", p->row_num); |
| } |
| } |