/*

------------------------------------------------------------------------------

A license is hereby granted to reproduce this software source code and
to create executable versions from this source code for personal,
non-commercial use.  The copyright notice included with the software
must be maintained in all copies produced.

THIS PROGRAM IS PROVIDED "AS IS". THE AUTHOR PROVIDES NO WARRANTIES
WHATSOEVER, EXPRESSED OR IMPLIED, INCLUDING WARRANTIES OF
MERCHANTABILITY, TITLE, OR FITNESS FOR ANY PARTICULAR PURPOSE.  THE
AUTHOR DOES NOT WARRANT THAT USE OF THIS PROGRAM DOES NOT INFRINGE THE
INTELLECTUAL PROPERTY RIGHTS OF ANY THIRD PARTY IN ANY COUNTRY.

Copyright (c) 1995, John Conover, All Rights Reserved.

Comments and/or bug reports should be addressed to:

    john@johncon.com (John Conover)

------------------------------------------------------------------------------

eval.c, evaluation for postfix notation

To evaluate the postfix stack, the postfix stack is scanned; if an
identifier is found the EVAL element that is referenced by the POSTFIX
element is pushed on the evaluation stack (using the "next" element to
establish the links;) if an operand is found, two EVAL elements are
pop'ed from the stack, the result of the boolean operation of the
number of matches found in the two elements is computed, and pushed
back on the stack-syntax for this operation is verified in postfix (),
in postfix.c

The heuristic logical boolean operations are defined as follows:

    if the operation is logical or, the sum of the matches are pushed
    on the stack

    if the operation is logical and, the sum of the matches are pushed
    on the stack

    if the operation is logical not, and the number of matches is
    non-zero, zero is pushed on the stack, otherwise, the number of
    matches found so far is pushed back on the stack

Note that this "relevance weighting" method describes a set theoretic
situation that could be considered counterintuitive between the
logical or and logical and, (depending on your point of view,) since
the intersection of a set of words in multiple documents, (ie.,
logical and) would seem to present a "stronger relevance" than the
union (ie., logical or) of a set of words in multiple
documents-however they have identical relevance values with this
methodology

There is one other comment that may be significant regarding relevance
determination of documents that are composed in one of the
standardized general markup languages, like TeX/LaTeX, or SGML-it may
be possible to "weight" the relevance of search matches on where words
are found in the structure of the document, for example, if the search
was for "numerical" and "methods," \chapter{Numerical Methods} would
be weighted "stronger" than if the words were found in
\section{Numerical Methods}, which in turn would be weighted
"stronger" than if the words were found in a paragraph. This would
permit relevance of a document to be determined by how author
structured the document.

For a detailed description of evaluating postfix notation, see, "Data
Structures Using C," Aaron M. Tenenbaum, Yedidyah Langsam, Moshe
J. Augenstein, Prentice Hall, Englewood Cliffs, New Jersey, 1990, ISBN
0-13-199746-7, pp 86.

To test this module, compile with -DTEST_SEARCHFILE

$Revision: 1.0 $
$Date: 1995/04/22 05:13:18 $
$Id: eval.c,v 1.0 1995/04/22 05:13:18 john Exp $
$Log: eval.c,v $
 * Revision 1.0  1995/04/22  05:13:18  john
 * Initial revision
 *

*/

#include "rel.h"

#ifndef LINT /* include rcsid only if not running lint */

static char rcsid[] = "$Id: eval.c,v 1.0 1995/04/22 05:13:18 john Exp $"; /* module version */
static char rcsid_h[] = EVAL_H_ID; /* module include version */

#endif

static EVAL *eval_stack = (EVAL *) 0; /* reference to the postfix evaluation stack */

#ifdef __STDC__

static void or (EVAL *element);
static void and (EVAL *element);
static void not (EVAL *element);
static void identifier (EVAL *element);

#else

static void or ();
static void and ();
static void not ();
static void identifier ();

#endif

/*

int allocate_eval (ELEMENT *element);

    allocate an EVAL element, and reference the function to call to
    handle the evaluation for this token

The algorithm is as follows:

    allocate the EVAL element

    set the the function to correspond to the precedence of the token
    (the precedence is also a unique identifier for the token type)

Usage is a call with a reference to the element from the postfix
stack, for example:

    if ((postfix_error = allocate_eval (new_element)) != NO_ERROR)
    {
        handle_error (postfix_error);
    }

The single argument, element, is a reference to the element from the
postfix stack

Returns zero if successful, non-zero if error

*/

#ifdef __STDC__

int allocate_eval (ELEMENT *element)

#else

int allocate_eval (element)
    ELEMENT *element;

#endif

{
    int retval = URMEM_ERR; /* return value, assume error allocating memory */

    if ((element->eval = (EVAL *) memalloc (sizeof (EVAL))) != (EVAL *) 0) /* allocate a new EVAL element for the token */
    {
        retval = NO_ERROR; /* assume no errors */
    }

    switch (element->precedence)
    {

        case LEFT: /* '(' grouping operator */

            retval = URSYN_ERR; /* can't be, syntax error */
            break;

        case OR: /* "or" operator */

            element->eval->function = (PTF) or; /* or operator function */
            break;

        case AND: /* "and" operator */

            element->eval->function = (PTF) and; /* and operator function */
            break;

        case NOT: /* "not" operator */

            element->eval->function = (PTF) not; /* not operator function */
            break;

        case RIGHT: /* ')' grouping operator */

            retval = URSYN_ERR; /* can't be, syntax error */
            break;

        case IDENTIFIER: /* a word */

            element->eval->function = (PTF) identifier; /* identifier operator function */
            break;

        case NONE: /* no token */

            retval = URSYN_ERR; /* can't be, syntax error */
            break;

        default:

            retval = URSYN_ERR; /* can't be, syntax error */
            break;

    }

    return (retval); /* return any errors */
}

/*

int postfix_eval (ELEMENT *postfix_stack);

    evaluate the postfix stack, referenced by postfix_stack

The algorithm is as follows:

    for each element on the postfix stack

    if the element is a token IDENTIFIER

        save the count of matches of the token

    call the functional operation for the element on the postfix stack

    the first element on the evaluation stack contains the relevance
    of the search, return it

Usage is a call with a reference to the element from the postfix
stack, for example:

    if ((value = postfix_eval (postfix_stack)) > 0)
    {
        handle_relevance (value);
    }

The single argument, postfix_stack, is a reference to the postfix
stack

Returns the computed relevance value

*/

#ifdef __STDC__

int postfix_eval (ELEMENT *postfix_stack)

#else

int postfix_eval (postfix_stack)
    ELEMENT *postfix_stack;

#endif

{
    ELEMENT *element = postfix_stack; /* reference to element on the postfix stack */

    eval_stack = (EVAL *) 0; /* null the postfix eval stack */

    while (element != (ELEMENT *) 0) /* for each element on the postfix stack */
    {

        if (element->precedence == IDENTIFIER) /* element represent an identifier? */
        {
            element->eval->value = element->pattern->count; /* yes, get the count of matches for this identifier */
        }

        (*element->eval->function) (element->eval); /* call the element's corresponding function operation */
        element = element->next; /* next element on the postfix stack */
    }

    return (eval_stack->value); /* the first element on the evaluation stack contains the computed relevance value */
}


/*

static void or (EVAL *element);

    compute the value for the "or" boolean operation

The algorithm is as follows:

    pop two evaluation elements off of the evaluation stack

    if either, or both, of the elements have search matches

        push the the sum of the matches in both elements back on the
        stack

    else

        push zero back on the stack

The single argument, element, is a reference to the element from the
postfix stack

Returns nothing

*/

#ifdef __STDC__

static void or (EVAL *element)

#else

static void or (element)
    EVAL *element;

#endif

{
    EVAL *operand1, /* top evaluation structure on the evaluation stack */
         *operand2; /* next evaluation structure on the evaluation stack */

    operand1 = POP (eval_stack); /* pop the top evaluation structure off the evaluation stack */
    operand2 = POP (eval_stack); /* pop the next evaluation structure off the evaluation stack */

    if (operand1->value != 0 || operand2->value != 0) /* either evaluation structure have matches? */
    {
        element->value = operand1->value + operand2->value; /* yes, the result is the sum of the matches */
    }

    else
    {
        element->value = 0; /* no, no matches */
    }

    PUSH (eval_stack, element); /* push the result back on the evaluation stack */
}


/*

static void and (EVAL *element);

    compute the value for the "and" boolean operation

The algorithm is as follows:

    pop two evaluation elements off of the evaluation stack

    if both of the elements have search matches

        push the the sum of the matches in both elements back on the
        stack

    else

        push zero back on the stack

The single argument, element, is a reference to the element from the
postfix stack

Returns nothing

*/

#ifdef __STDC__

static void and (EVAL *element)

#else

static void and (element)
    EVAL *element;

#endif

{
    EVAL *operand1, /* top evaluation structure on the evaluation stack */
         *operand2; /* next evaluation structure on the evaluation stack */

    operand1 = POP (eval_stack); /* pop the top evaluation structure off the evaluation stack */
    operand2 = POP (eval_stack); /* pop the next evaluation structure off the evaluation stack */

    if (operand1->value == 0 || operand2->value == 0) /* either evaluation structure no matches? */
    {
        element->value = 0; /* yes, no matches */
    }

    else
    {
        element->value = operand1->value + operand2->value; /* no, the result is the sum of the matches */
    }

    PUSH (eval_stack, element); /* push the result back on the evaluation stack */
}

/*

static void not (EVAL *element);

    compute the value for the "not" boolean operation

The algorithm is as follows:

    pop two evaluation elements off of the evaluation stack

    if the last element has matches

        puch zero on the stack

    else

        push the the matches of the first element on the stack stack

The single argument, element, is a reference to the element from the
postfix stack

Returns nothing

*/

#ifdef __STDC__

static void not (EVAL *element)

#else

static void not (element)
    EVAL *element;

#endif

{
    EVAL *operand1, /* top evaluation structure on the evaluation stack */
         *operand2; /* next evaluation structure on the evaluation stack */

    operand1 = POP (eval_stack); /* pop the top evaluation structure off the evaluation stack */
    operand2 = POP (eval_stack); /* pop the next evaluation structure off the evaluation stack */

    if (operand1->value != 0) /* first evaluation structure have matches? */
    {
        element->value = 0; /* yes, no matches */
    }

    else
    {
        element->value = operand2->value; /* no, matches are the same as the second element structure */
    }

    PUSH (eval_stack, element); /* push the result back on the evaluation stack */
}

/*

static void identifier (EVAL *element);

    compute the value for the "identifier" operation

The algorithm is as follows:

    puch the element on the evaluation stack

The single argument, element, is a reference to the element from the
postfix stack

Returns nothing

*/

#ifdef __STDC__

static void identifier (EVAL *element)

#else

static void identifier (element)
    EVAL *element;

#endif

{
    PUSH (eval_stack, element); /* push the eval struture on the eval stack */
}