partset.c

一个非常好的检索工具

continu: ;
   }

    /*************************************************************/
    /* We now partition all the unique sets in the hash table    */
    /* based on the number of elements they contain...           */
    /* NEXT is also used to construct these lists.  Recall that  */
    /* the unique elements are roots of lists. Hence, their      */
    /* corresponding HEAD elements are used, but their           */
    /* corresponding NEXT field is still unused.                 */
    /*************************************************************/
    for (i = 0; i <= set_size; i++)
         partition[i] = NIL;

    for (index = 1; index <= collection_size; index++)
    {
        if (head[index] != OMEGA) /* Subset representative */
        {
            size = element_size[index];
            next[index] = partition[size];
            partition[size] = index;
        }
    }

    /*************************************************************/
    /*     ...Construct a list of all the elements of PARTITION  */
    /* that are not empty.  Only elements in this list will be   */
    /* considered for subset merging later ...                   */
    /* Note that since the elements of PARTITION are added to    */
    /* the list in ascending order and in stack-fashion, the     */
    /* resulting list will be sorted in descending order.        */
    /*************************************************************/
    size_root = NIL;
    for (i = 0; i <= set_size; i++)
    {
        if (partition[i] != NIL)
        {
            size_list[i] = size_root;
            size_root = i;
        }
    }

    /*************************************************************/
    /* Merge subsets that are mergeable using heuristic described*/
    /* above.  The vector IS_A_BASE is used to mark subsets      */
    /* chosen as bases.                                          */
    /*************************************************************/
    for (i = 0; i <= collection_size; i++)
        is_a_base[i] = FALSE;
    for (size = size_root; size != NIL; size = size_list[size])
    { /* For biggest partition there is */
        for (base_set = partition[size];
             base_set != NIL; base_set = next[base_set])
        { /* For each set in it... */
            /*****************************************************/
            /* Mark the state as a base state, and initialize    */
            /* its stack.  The list representing the stack will  */
            /* be circular...                                    */
            /*****************************************************/
            is_a_base[base_set] = TRUE;
            stack[base_set] = base_set;

            /**************************************************************/
            /* For remaining elements in partitions in decreasing order...*/
            /**************************************************************/

            for (next_size = size_list[size];
                 next_size != NIL; next_size = size_list[next_size])
            {
                previous = NIL;           /* mark head of list */

                /**************************************************/
                /* Iterate over subsets in the partition until we */
                /* find one that is a subset of the subset on top */
                /* of the stack.  If none is found, we go on to   */
                /* the next element of the partition. Otherwise,  */
                /* we push the new subset on top of the stack and */
                /* go on to the next element of the partition.    */
                /* INDEX identifies the state currently on top    */
                /* of the stack.                                  */
                /**************************************************/
                for (subset = partition[next_size];
                     subset != NIL;
                     previous = subset, subset = next[subset])
                {
                    index = stack[base_set];
                    B_ASSIGN_SET(temp_set, 0, collection, index, bctype);
                    B_SET_UNION(temp_set, 0, collection, subset, bctype);

                    /* SUBSET is a subset of INDEX?*/
                    if (equal_sets(temp_set, 0, collection, index, bctype))
                    {
                        if (previous == NIL)
                            partition[next_size] = next[subset];
                        else
                            next[previous] = next[subset];
                        stack[subset] = stack[base_set];
                        stack[base_set] = subset;
                        break; /* for (subset = partition[next_size]... */
                    }
                }
            }
        }
    }

    /*************************************************************/
    /* Iterate over the states in the order in which they are to */
    /* be output, and assign an offset location to each state.   */
    /* Notice that an extra element is added to the size of each */
    /* base subset for the "fence" element.                      */
    /*************************************************************/
    offset = 1;
    for (i= 1; i<= collection_size; i++)
    {
        base_set = list[i];
        if (is_a_base[base_set])
        {
            start[base_set] = offset;
            /***********************************************************/
            /* Assign the same offset to each subset that is           */
            /* identical to the BASE_SET subset in question. Also,     */
            /* mark the fact that this is a copy by using the negative */
            /* value of the OFFSET.                                    */
            /***********************************************************/
            for (index = head[base_set]; index != NIL; index = next[index])
                start[index] = - start[base_set];

            size = element_size[base_set] + 1;
            offset += size;
            SHORT_CHECK(offset);

            /*********************************************************/
            /* Now, assign offset values to each subset of the       */
            /* BASE_SET. Once again, we mark them as sharing elements*/
            /* by using the negative value of the OFFSET.            */
            /* Recall that the stack is constructed as a circular    */
            /* list.  Therefore, its end is reached when we go back  */
            /* to the root... In this case, the root is already      */
            /* processed, so we stop when we reach it.               */
            /*********************************************************/
            for (index = stack[base_set];
                 index != base_set; index = stack[index])
            {
                size = element_size[index] + 1;
                start[index] = -(offset - size);

                /*****************************************************/
                /* INDEX identifies a subset of BASE_SET. Assign the */
                /* same offset as INDEX to each subset j that is     */
                /* identical to the subset INDEX.                    */
                /*****************************************************/
                for (j = head[index]; j != NIL; j = next[j])
                    start[j] = start[index];
            }
        }
    }
    start[collection_size+1] = offset;

    ffree(size_list);
    ffree(partition);
    ffree(domain_link);
    ffree(head);
    ffree(next);
    ffree(is_a_base);
    ffree(temp_set);

    return;
}


/****************************************************************************/
/*                               EQUAL_SETS:                                */
/****************************************************************************/
/* EQUAL_SETS checks to see if two sets are equal and returns True or False */
/****************************************************************************/
static BOOLEAN equal_sets(SET_PTR set1, int indx1,
                          SET_PTR set2, int indx2, int bound)
{
    register int i;

    for (i = 0; i < bound; i++)
    {
        if (set1[indx1 * bound + i] != set2[indx2 * bound + i])
           return(0);
    }

    return(TRUE);
}