diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /indexing/glo+idxtex/idxrange.c |
Initial commit
Diffstat (limited to 'indexing/glo+idxtex/idxrange.c')
-rw-r--r-- | indexing/glo+idxtex/idxrange.c | 713 |
1 files changed, 713 insertions, 0 deletions
diff --git a/indexing/glo+idxtex/idxrange.c b/indexing/glo+idxtex/idxrange.c new file mode 100644 index 0000000000..b4d9fb6a8a --- /dev/null +++ b/indexing/glo+idxtex/idxrange.c @@ -0,0 +1,713 @@ +/* #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 <stdlib.h> +#include <stdio.h> +#include <io.h> +#define F_OK 0 /* access(): File exists */ +#else +#include <sys/file.h> +#endif +#include <string.h> +#include <malloc.h> +#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; +} |