path: root/indexing/glo+idxtex/idxrange.c

/* #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;
}