/* #module IdxRange "3-001" *********************************************************************** * * * The software was developed at the Monsanto Company and is provided * * "as-is". Monsanto Company and the auther disclaim all warranties * * on the software, including without limitation, all implied warran- * * ties of merchantabilitiy and fitness. * * * * This software does not contain any technical data or information * * that is proprietary in nature. It may be copied, modified, and * * distributed on a non-profit basis and with the inclusion of this * * notice. * * * *********************************************************************** */ /* * Module Name: IdxRange * * Author: R L Aurbach CR&DS MIS Group 07-Apr-1987 * * Function: * Examine the list of page references to build range references. * * Modification History: * * Version Initials Date Description * ------------------------------------------------------------------------ * 1-001 RLA 07-Apr-1987 Original Code * 1-002 RLA 14-Apr-1987 Fix algorithm for processing ranges * which contain highlights. * 3-001 F.H. 17-May-1991 converted to portable C */ /* * Module IdxRange - Module-Wide Data Description Section * * Include Files: */ #ifdef MSDOS #include #include #include #define F_OK 0 /* access(): File exists */ #else #include #endif #include #include #include "IdxDef.h" /* * Module Definitions: */ #define IDX_K_START 1 /* Start of range */ #define IDX_K_MIDDLE 2 /* Middle of range */ #define IDX_K_END 3 /* End of range */ #define IDX_K_SIMPLE 0 /* Simple page-ref */ #define IDX_K_COMPLEX 1 /* Complex page-ref */ #define TRUE 1 #define FALSE 0 typedef struct { char *vol; /* Volume string ptr */ char *page_dsc; /* Page-ref string */ char highlight; /* Highlight flag */ char adjacent; /* Adjacency flag */ char flag; /* Range type flag */ char type; /* Page-ref type flag */ int start; /* Start of range */ } TABLE, *TABLE_PTR; typedef struct { char *vol; /* Volume string ptr */ char *chapter; /* Chapter string */ int page; /* Page number */ char type; /* Page-ref type flag */ } CMP, *CMP_PTR; /* * Global Declarations: */ /* * Static Declarations: */ #ifdef MSDOS void idx_build_range(TREE_PTR node); void idx_page_parse(TABLE_PTR elem, CMP_PTR cmp); int idx_is_adjacent(CMP_PTR curr, CMP_PTR prev); void idx_deallocate_pglist(TREE_PTR node); void idx_build_new_pglist(TREE_PTR node, TABLE_PTR table, int size); void idx_allocate_new_pgnode(PGNODE_PTR *ptr, TREE_PTR node); #else void idx_build_range(); void idx_page_parse(); int idx_is_adjacent(); void idx_deallocate_pglist(); void idx_build_new_pglist(); void idx_allocate_new_pgnode(); #endif static char *dash = "-"; static char *simple = "--"; static char *complex = " to "; /* * External References: */ #ifdef MSDOS extern int strposition(char *str, char *e_array, int st); #else int strposition(); #endif /* * Functions Called: */ /* * Function Idx_Build_Range - Documentation Section * * Discussion: * Examine a list of page references. If the list contains any pages * which are in consecutive order, build a new list of page references * which contain one or more range specifications. * * Calling Synopsis: * Call Idx_Build_Range (node) * * Inputs: * node -> pointer to the current node of the item tree. * * Outputs: * none -> pointer to the current node of the item tree. * * Return Value: * none * * Global Data: * none * * Files Used: * none * * Assumed Entry State: * none * * Normal Exit State: * none * * Error Conditions: * none * * Algorithm: * A. Count the number of page references in the current list. * 1. If less than 2, there is nothing to do. * B. Allocate a TABLE structure big enough to hold all the references. * C. For each reference, * 1. Fill in the TABLE entry. * 2. Call Idx_Page_Parse to parse the page reference and place the * results of the parse operation in the "new" CMP structure. * 3. Call Idx_Is_Adjacent to compare the information in the "old" * and "new" CMP structures to determine if the page number is * adjacent to the previous one. * 4. If it is, * a. Set the adjacent flag in the TABLE entry. * b. Set the "ranges_found" flag. * D. If no ranges were found, * 1. Deallocate the TABLE. * 2. Return. * E. Else, * 1. Process the TABLE to set up the "flag" and "start" fields. * 2. Call Idx_Deallocate_PgList to deallocate the old page-refs. * 3. Call Idx_Build_New_PgList to allocate a new page-ref list. * 4. Deallocate the TABLE. * * Special Notes: * none */ /* * Function Idx_Build_Range - Code Section */ void idx_build_range(node) TREE_PTR node; /* Current tree node */ { /* * Local Declarations */ PGNODE_PTR pgnode; /* Current page node */ int ref_ct = 0; /* Number of page nodes */ TABLE_PTR table; /* Local structure pointer */ int ranges_found = FALSE; /* Ranges found flag */ CMP old; /* Parse struct for prev ref */ CMP new; /* Parse struct for curr ref */ int i, j; /* Table index */ /* * Module Body */ /* * Count the number of page references for the current tree node. * If there are less than 2, there is nothing to do -- no ranges are possible. */ pgnode = node->pghead; while (pgnode != 0) { ref_ct++; pgnode = pgnode->link; } if (ref_ct < 2) return; /* * Allocate an internal data table sufficiently large to contain all of the * existing page reference entries. */ table = (TABLE_PTR) malloc ((unsigned int)ref_ct * sizeof(TABLE)); if (table == 0) return; /* * Initialize the previous page reference parse structure to null. */ old.vol = 0; old.page = 0; old.type = IDX_K_SIMPLE; pgnode = node->pghead; /* * For each page reference in the page reference list, we must build the * appropriate entry in the internal data table. To do this, we first * initialize the entry using the available data. */ for (i = 0; i < ref_ct; i++) { table[i].vol = pgnode->vol; table[i].page_dsc = pgnode->page_dsc; table[i].highlight = pgnode->highlight; table[i].adjacent = FALSE; table[i].flag = IDX_K_NONE; table[i].type = IDX_K_SIMPLE; table[i].start = 0; pgnode = pgnode->link; /* * Now we parse the page descriptor and fill out the data structure used * for comparison and compare it against the previous page reference. If * the pages are consecutive, we flag the table entry and set the ranges_found * flag. Finally, we copy the new structure to the old structure to prepare * for the next iteration. */ idx_page_parse (&table[i], &new); if (idx_is_adjacent (&new, &old)) { table[i].adjacent = TRUE; ranges_found = TRUE; } free((char *)&old.chapter); old = new; } /* * Since we are now done with the "old" and "new" structures, deallocate * the dynamic strings they reference. (So that we don't forget). */ free((char *)&old.chapter); /* Just once, please! */ /* * If we haven't found any ranges, then all of this analysis was for nought. * We just deallocate the table and leave, with the initial list intact. */ if (!ranges_found) { free((char *)&table); return; } /* * At this point, we know we have found at least one range, so we have work * to do. First, we need to process the table so that the "flag" and "start" * fields are set up correctly. */ for (i = 1; i < ref_ct; i++) { /* * If the current entry is part of a range and has the FOLLOW highlight, then * make sure that every element of the range has the same highlight. */ if (table[i].adjacent && table[i].highlight == IDX_K_FOLLOW) { if (table[i-1].flag == IDX_K_NONE) table[i-1].highlight = IDX_K_FOLLOW; else for (j = table[i-1].start; j < i; j++) table[j].highlight = IDX_K_FOLLOW; } /* * If the current entry is part of a range which has the FOLLOW highlight, then * it should have that highlight also. */ if (table[i].adjacent && table[i-1].highlight == IDX_K_FOLLOW) table[i].highlight = IDX_K_FOLLOW; /* * If the current entry is part of a range, then update the flag and start * values in the table. */ if (table[i].adjacent && (table[i].highlight == table[i-1].highlight)) { if (table[i-1].flag == IDX_K_NONE) { table[i-1].flag = IDX_K_START; table[i-1].start = i-1; } table[i].flag = IDX_K_MIDDLE; table[i].start = table[i-1].start; } /* * If the entry is not part of a range, then if the preceeding entry was part * of a range, it was the end of that range. Mark it so. */ else { if (table[i-1].flag == IDX_K_MIDDLE) table[i-1].flag = IDX_K_END; } } /* * If the last entry in the table was part of a range, it hasn't been correctly * marked that way yet. Do so now. */ if (table[ref_ct-1].flag == IDX_K_MIDDLE) table[ref_ct-1].flag = IDX_K_END; /* * At this point, we know we are going to create a new page-ref list, so we * can deallocate the old list. Note that we don't need to free any strings, * because they are all contained in the data table... */ idx_deallocate_pglist (node); /* * Now we use the information in the table to build the new page-ref list. */ idx_build_new_pglist (node, table, ref_ct); /* * We are done. To clean up correctly, we must deallocate the table. To * do this, we first deallocate any strings which are defined in the table, * then deallocate the table. This should clean up virtual memory usage * nicely. */ for (i = 0; i < ref_ct; i++) free((char *)table[i].page_dsc); free ((char *)&table); } /* * Function Idx_Page_Parse - Documentation Section * * Discussion: * Parse a page number into its component parts. * * Calling Synopsis: * call Idx_Page_Parse (elem, cmp) * * Inputs: * elem -> is an element of the table array, describing the * current page reference. It is passed by reference. * * Outputs: * elem -> is an element of the table array, describing the * current page reference. It is passed by reference. * The "type" flag is updated. * * cmp -> is the comparison data structure into which the data * for this page reference is parsed. It is passed by * reference. * * Return Value: * none * * Global Data: * none * * Files Used: * none * * Assumed Entry State: * none * * Normal Exit State: * none * * Error Conditions: * none * * Algorithm: * A. Initialize the output data structure. * B. If the input string contains a '-', * 1. Copy the characters prior to the '-' to the chapter string. * 2. Set the flags to mark this page number as complex. * C. Skip over any '-'s. * D. Convert the rest of the string to an integer. * * Special Notes: * none */ /* * Function Idx_Page_Parse - Code Section */ void idx_page_parse (elem, cmp) TABLE_PTR elem; /* Pointer to a table entry */ CMP_PTR cmp; /* Pointer to a CMP structure */ { /* * Local Declarations */ int i; /* String Index */ char *temp; /* * Module Body */ /* Initialize the cmp structure. */ cmp->vol = elem->vol; cmp->page = 0; cmp->type = IDX_K_SIMPLE; /* * This routine assumes that the chapter string is delimited by one or more * "-" characters. Determine if the page reference string contains such a * delimiter. If it does, then copy the chapter portion of the string to * the output string and set the "type" field to IDX_K_COMPLEX. */ i = strposition(elem->page_dsc, dash, 0); if (i != -1) { i--; (void)strncpy(cmp->chapter, elem->page_dsc, i); cmp->type = IDX_K_COMPLEX; elem->type = IDX_K_COMPLEX; } /* Skip all dash characters. */ while (elem->page_dsc[i] == '-') i++; if (i<0) i=0; /* Convert the page number to an integer */ temp = strdup(&elem->page_dsc[i]); (void)sscanf(temp, "%d", &cmp->page); } /* * Function Idx_Is_Adjacent - Documentation Section * * Discussion: * Compare two page references and determine if the first is adjacent * to the second. * * Calling Synopsis: * boolean = Idx_Is_Adjacent (curr, prev) * * Inputs: * curr -> is the CMP data structure for the current page ref, * passed by reference. * * prev -> is the CMP data structure for the previous page ref, * passed by reference. * * Outputs: * none * * Return Value: * boolean -> is a boolean result, passed by value. * * Global Data: * none * * Files Used: * none * * Assumed Entry State: * none * * Normal Exit State: * boolean = TRUE Pages are consecutive. * boolean = FALSE Pages are not consecutive. * * Error Conditions: * none * * Algorithm: * A. If the page refs don't have the same type, return FALSE. * B. If the page refs don't have the same vol-string ptr, return FALSE. * C. If the page ref type is COMPLEX, * 1. If the two chapter strings are not the same, return FALSE. * D. If the page numbers are not consecutive, return FALSE. * E. Return TRUE. * * Special Notes: * none */ /* * Function Idx_Is_Adjacent - Code Section */ int idx_is_adjacent (curr, prev) CMP_PTR curr; /* Current page-ref structure */ CMP_PTR prev; /* Previous page-ref structure */ { /* * Local Declarations */ /* * Module Body */ if (curr->type != prev->type) return(FALSE); if (prev->vol == 0) return(FALSE); if ((strcmp(curr->vol,prev->vol)) != 0) return(FALSE); if (curr->type == IDX_K_COMPLEX) if (strcmp(curr->chapter, prev->chapter) != 0) return(FALSE); if ((curr->page == prev->page) || (curr->page == (prev->page + 1))) return(TRUE); return(FALSE); } /* * Function Idx_Deallocate_PgList - Documentation Section * * Discussion: * Deallocate the old page list for the current tree node. * * Calling Synopsis: * call Idx_Deallocate_PgList (node) * * Inputs: * node -> is the current tree node, passed by ref. * * Outputs: * node -> is the current tree node, passed by ref. * * Return Value: * none * * Global Data: * none * * Files Used: * none * * Assumed Entry State: * none * * Normal Exit State: * none * * Error Conditions: * none * * Algorithm: * A. While the page listhead is not empty, * 1. Unlink the current top of the list. * 2. Deallocate it. * * Special Notes: * none */ /* * Function Idx_Deallocate_PgList - Code Section */ void idx_deallocate_pglist (node) TREE_PTR node; { /* * Local Declarations */ PGNODE_PTR curr; /* Current page node */ /* * Module Body */ while (node->pghead != 0) { curr = node->pghead; node->pghead = curr->link; free((char *)curr); } } /* * Function Idx_Build_New_PgList - Documentation Section * * Discussion: * Use the data table to construct a new pagelist. * * Calling Synopsis: * call Idx_Build_New_PgList (node, table, size) * * Inputs: * node -> is the current tree node, passed by reference. * * table -> is the data table, passed by reference. * * size -> is the number of elements in the table, passed by value. * * Outputs: * node -> is the current tree node, passed by reference. The * new page list is linked to the pghead. * * Return Value: * none * * Global Data: * none * * Files Used: * none * * Assumed Entry State: * The tree node has a null page list. * * Normal Exit State:* * none * * Error Conditions: * none * * Algorithm: * A. For each entry in the table, * 1. If the entry is not part of a range, * a. Allocate a new element for the page list. * b. Fill it out. * 2. If the entry is the beginning of a range, * a. Allocate a new element for the page list. * b. Begin filling out the page list element. * 3. If the entry is the middle of a range, * a. Ignore it. * 4. If the entry is the end of a range, * a. Complete filling out the page list element. * * Special Notes:o * nonet */ /* * Function Idx_Build_New_PgList - Code Sectionm */ void idx_build_new_pglist (node, table, size) TREE_PTR node; TABLE_PTR table; int size; { /* * Local Declarations */ PGNODE_PTR ptr = 0; /* New PageRef Pointer */ int i; /* Current table entry */ /* * Module Body */ for (i = 0; i < size; i++) { switch (table[i].flag) { case IDX_K_NONE: idx_allocate_new_pgnode(&ptr, node); ptr->vol = table[i].vol; (void)strcpy(ptr->page_dsc, table[i].page_dsc); ptr->highlight = table[i].highlight; break; case IDX_K_START: idx_allocate_new_pgnode(&ptr, node); ptr->vol = table[i].vol; (void)strcpy(ptr->page_dsc, table[i].page_dsc); if ((ptr->highlight = table[i].highlight) == IDX_K_FOLLOW) break; if (table[i].type == IDX_K_SIMPLE) (void)strcat(ptr->page_dsc, simple); else (void)strcat(ptr->page_dsc, complex); break; case IDX_K_MIDDLE: break; case IDX_K_END: if (ptr->highlight != IDX_K_FOLLOW) (void)strcat(ptr->page_dsc, table[i].page_dsc); break; } } } /* * Function Idx_Allocate_New_PgNode - Documentation Section * * Discussion: * Allocate and link a new page-ref node into the current list. * * Calling Synopsis: * call Idx_Allocate_New_PgNode(ptr, node) * * Inputs: * ptr -> is the current page-ref node pointer, passed by ref. * * node -> is the current tree-node pointer. * * Outputs: * ptr -> is the new page-ref pointer, passed by reference.r * * Return Value: * none * * Global Data: * none * * Files Used: * nones * * Assumed Entry State: * none * * Normal Exit State: * none; * * Error Conditions: * none * * Algorithm: * A. Allocate a new pgnode. * B. Link it into the chain after the current pointer. * * Special Notes: * none */ /* * Function Idx_Allocate_New_PgNode - Code Section */ void idx_allocate_new_pgnode (ptr, node) PGNODE_PTR *ptr; /* Page-Ref Node Pointer */ TREE_PTR node; /* Node pointer */ { /* * Local Declarations */ PGNODE_PTR new; /* New Page-Ref Node Ptr */ /* * Module Body */ new = (PGNODE_PTR) malloc(sizeof(PGNODE)); new->link = 0; new->vol = 0; new->highlight = IDX_K_NONE; if ((*ptr) == 0) node->pghead = new; else (*ptr)->link = new; new->page_dsc = malloc(133); *ptr = new; }