home *** CD-ROM | disk | FTP | other *** search
/ Internet Publisher's Toolbox 2.0 / Internet Publisher's Toolbox.iso / internet / ntserver / wtsource / boolean_.c next >
Encoding:
C/C++ Source or Header  |  1994-11-30  |  16.1 KB  |  515 lines
  1. /* 
  2.  * boolean_op.c -- 
  3.  * SCCS Status     : %W%        %G%
  4.  * Author          : Huynh Quoc T. Tung
  5.  * Created On      : Sun Oct 17 16:40:46 1993
  6.  * Last Modified By: Huynh Quoc T. Tung
  7.  * Last Modified On: Tue Oct 19 08:36:47 1993
  8.  * Update Count    : 2
  9.  * Status          : Unknown, Use with caution!
  10.  */
  11.  
  12. #include <stdio.h>
  13. #include <string.h>
  14. #include "irfiles.h"
  15. #include "boolean_op.h"
  16.  
  17. struct node
  18. { 
  19.   long key; 
  20.   struct node *next;
  21. };
  22. struct node *head, *z, *t;
  23.  
  24. extern long number_of_qwords;
  25. extern double *document_score_array;
  26. extern search_result_struct* search_result_array;
  27.  
  28. search_result_struct *end_result = NULL;
  29.  
  30. boolean IsOperator(op)
  31.      char *op;
  32. {
  33.   if(!strcmp(op,"and") ||
  34.      !strcmp(op,"or") ||
  35.      !strcmp(op,"not"))
  36.     return(true);
  37.   else return(false);
  38. }
  39.  
  40. void stackinit()
  41. {
  42.   head = (struct node *) malloc(sizeof (* head));
  43.   z = (struct node *) malloc(sizeof(* z));
  44.   head->next = z; 
  45.   head->key = 0;
  46.   z->next = z;
  47. }
  48.  
  49. void push(v)
  50.      long v;
  51. {
  52.   t = (struct node *) malloc(sizeof(* t));
  53.   t->key = v;
  54.   t->next = head->next;
  55.   head->next = t;
  56. }
  57.  
  58. long pop()
  59. {
  60.   long x;
  61.   
  62.   t = head->next;
  63.   head->next = t->next;
  64.   x = t->key;
  65.   free(t);
  66.   return x;
  67. }
  68.  
  69. int stackempty()
  70. {
  71.   return head->next == z;
  72. }
  73.  
  74. void Union(result, set1, set2)
  75.      search_result_struct *result;
  76.      search_result_struct *set1;
  77.      search_result_struct *set2;
  78. {
  79.   while((set1->number_of_hits != 0) &&
  80.         (set2->number_of_hits != 0)) {
  81.     if(set1->doc_ids_array->doc_id < set2->doc_ids_array->doc_id) {
  82.       result->doc_ids_array->doc_id = set1->doc_ids_array->doc_id;
  83.       result->doc_ids_array->score = set1->doc_ids_array->score;
  84.       ++result->number_of_hits;
  85.       ++result->doc_ids_array ;
  86.       --set1->number_of_hits;
  87.       ++set1->doc_ids_array; 
  88.     }
  89.     else if(set1->doc_ids_array->doc_id > set2->doc_ids_array->doc_id) {
  90.       result->doc_ids_array->doc_id = set2->doc_ids_array->doc_id;
  91.       result->doc_ids_array->score = set2->doc_ids_array->score;
  92.       ++result->number_of_hits;
  93.       ++result->doc_ids_array ;
  94.       --set2->number_of_hits;
  95.       ++set2->doc_ids_array;
  96.     }
  97.     else { /* doc_id1 == doc_id2 { */
  98.       result->doc_ids_array->doc_id = set1->doc_ids_array->doc_id;
  99.       result->doc_ids_array->score = set1->doc_ids_array->score + set2->doc_ids_array->score;
  100.       ++result->number_of_hits;
  101.       ++result->doc_ids_array ;
  102.       --set1->number_of_hits; --set2->number_of_hits;
  103.       ++set1->doc_ids_array; ++set2->doc_ids_array;
  104.     }
  105.   }
  106.   if((set1->number_of_hits == 0) &&
  107.      (set2->number_of_hits != 0)) {
  108.     memcpy((char *)result->doc_ids_array, 
  109.            set2->doc_ids_array, 
  110.            set2->number_of_hits * sizeof(doc_descr_struct));
  111.     set2->doc_ids_array += set2->number_of_hits;
  112.     result->doc_ids_array += set2->number_of_hits;
  113.     result->number_of_hits += set2->number_of_hits;
  114.     set2->number_of_hits = 0;
  115.   }
  116.   else if((set1->number_of_hits != 0) &&
  117.           (set2->number_of_hits == 0)) {
  118.     memcpy((char *)result->doc_ids_array, 
  119.            set1->doc_ids_array, 
  120.            set1->number_of_hits * sizeof(doc_descr_struct));
  121.     set1->doc_ids_array += set1->number_of_hits;
  122.     result->doc_ids_array += set1->number_of_hits;
  123.     result->number_of_hits += set1->number_of_hits;
  124.     set1->number_of_hits = 0;
  125.   }
  126. }
  127.  
  128. void Or_Operator(operand1, operand2)
  129.      long operand1;
  130.      long operand2;
  131. {
  132.   search_result_struct *op1, *op2;
  133.   long doc_score_size = sizeof(search_result_struct);
  134.   long doc_ids_array_size = sizeof(doc_descr_struct);
  135.   long op1_number_of_hits, op2_number_of_hits;
  136.   
  137.   op1 = &search_result_array[operand1];
  138.   op2 = &search_result_array[operand2];
  139.   op1_number_of_hits = op1->number_of_hits;
  140.   op2_number_of_hits = op2->number_of_hits;
  141.   
  142.   if(op1->number_of_hits == 0) {
  143.     if(op1->doc_ids_array != NULL)
  144.       s_free(op1->doc_ids_array);
  145.     if(op2->number_of_hits > 0) {
  146.       end_result->doc_ids_array = 
  147.         (doc_descr_struct *)
  148.           s_realloc(end_result->doc_ids_array, 
  149.                     op2->number_of_hits * doc_ids_array_size);
  150.       memcpy((char *)end_result->doc_ids_array, 
  151.              (char *)op2->doc_ids_array, 
  152.              doc_ids_array_size * op2->number_of_hits);
  153.     }
  154.     end_result->number_of_hits = op2->number_of_hits;
  155.     push(op2->word_id);
  156.   }
  157.   else if(op2->number_of_hits == 0) {
  158.     if(op2->doc_ids_array != NULL)
  159.       s_free(op2->doc_ids_array);
  160.     if(op1->number_of_hits > 0) {
  161.       end_result->doc_ids_array = 
  162.         (doc_descr_struct *)
  163.           s_realloc(end_result->doc_ids_array, 
  164.                     op1->number_of_hits * doc_ids_array_size);
  165.       memcpy((char *)end_result->doc_ids_array, 
  166.              (char *)op1->doc_ids_array, 
  167.              doc_ids_array_size * op1->number_of_hits);
  168.     }
  169.     end_result->number_of_hits = op1->number_of_hits;
  170.     push(op1->word_id);
  171.   } 
  172.   else if((op1->number_of_hits != 0) &&
  173.           (op2->number_of_hits != 0)) { 
  174.     end_result->doc_ids_array = 
  175.       (doc_descr_struct *)
  176.         s_realloc(end_result->doc_ids_array,
  177.                   (op1->number_of_hits + op2->number_of_hits) * 
  178.                   doc_ids_array_size);
  179.     end_result->number_of_hits = 0;
  180.     
  181.     Union(end_result, op1, op2);
  182.     
  183.     op1->doc_ids_array -= op1_number_of_hits - op1->number_of_hits;
  184.     op2->doc_ids_array -= op2_number_of_hits - op2->number_of_hits;
  185.     end_result->doc_ids_array -= end_result->number_of_hits;
  186.     op2->number_of_hits = end_result->number_of_hits;
  187.     s_free(op1->doc_ids_array);
  188.     if(end_result->number_of_hits > 0) {
  189.       op2->doc_ids_array = 
  190.         (doc_descr_struct *)
  191.           s_realloc(op2->doc_ids_array, 
  192.                     end_result->number_of_hits * doc_ids_array_size);
  193.       memcpy((char *)op2->doc_ids_array, 
  194.              (char *)end_result->doc_ids_array, 
  195.              end_result->number_of_hits * doc_ids_array_size);
  196.     }
  197.     else {
  198.       op2->number_of_hits = end_result->number_of_hits;
  199.       s_free(op2->doc_ids_array);
  200.     }
  201.     push(op2->word_id);
  202.   }
  203. }
  204.  
  205. void Intersection(result, set1, set2)
  206.      search_result_struct * result;
  207.      search_result_struct * set1;
  208.      search_result_struct * set2;
  209. {
  210.   while((set1->number_of_hits != 0) &&
  211.         (set2->number_of_hits != 0)) {
  212.     if(set1->doc_ids_array->doc_id == set2->doc_ids_array->doc_id) {
  213.       result->doc_ids_array->doc_id = set1->doc_ids_array->doc_id;
  214.       result->doc_ids_array->score = set1->doc_ids_array->score + set2->doc_ids_array->score;
  215.       ++result->number_of_hits;
  216.       ++result->doc_ids_array ;
  217.       --set1->number_of_hits; --set2->number_of_hits;
  218.       ++set1->doc_ids_array ; ++set2->doc_ids_array ;
  219.     }
  220.     else if(set1->doc_ids_array->doc_id < set2->doc_ids_array->doc_id) {
  221.       --set1->number_of_hits;
  222.       ++set1->doc_ids_array ;
  223.     }
  224.     else /* doc_id1 > doc_id2 */
  225.       {
  226.         --set2->number_of_hits;
  227.         ++set2->doc_ids_array ;
  228.       }
  229.   }
  230. }
  231.  
  232. void And_Operator(operand1, operand2)
  233.      long operand1;
  234.      long operand2;
  235. {
  236.   search_result_struct *op1, *op2;
  237.   long doc_score_size = sizeof(search_result_struct);
  238.   long doc_ids_array_size = sizeof(doc_descr_struct);
  239.   long op1_number_of_hits, op2_number_of_hits;
  240.   
  241.   op1 = &search_result_array[operand1];
  242.   op2 = &search_result_array[operand2];
  243.   op1_number_of_hits = op1->number_of_hits;
  244.   op2_number_of_hits = op2->number_of_hits;
  245.   
  246.   if(op1->number_of_hits == 0) {
  247.     end_result->number_of_hits = 0;
  248.     if(op1->doc_ids_array != NULL)
  249.       s_free(op1->doc_ids_array);
  250.     if(op2->doc_ids_array != NULL)
  251.       s_free(op2->doc_ids_array);
  252.     push(op1->word_id);
  253.   }
  254.   else if(op2->number_of_hits == 0) {
  255.     end_result->number_of_hits = 0;
  256.     if(op1->doc_ids_array != NULL)
  257.       s_free(op1->doc_ids_array);
  258.     if(op2->doc_ids_array != NULL)
  259.       s_free(op2->doc_ids_array);
  260.     push(op2->word_id);
  261.   }
  262.   else if((op1->number_of_hits != 0) &&
  263.           (op2->number_of_hits != 0)) {
  264.     if(op1->number_of_hits > op2->number_of_hits)
  265.       end_result->doc_ids_array = 
  266.         (doc_descr_struct *)
  267.           s_realloc(end_result->doc_ids_array,
  268.                     op2->number_of_hits * doc_ids_array_size);
  269.     else
  270.       end_result->doc_ids_array = 
  271.         (doc_descr_struct *)
  272.           s_realloc(end_result->doc_ids_array,
  273.                     op1->number_of_hits * doc_ids_array_size);
  274.     end_result->number_of_hits = 0;
  275.  
  276.     Intersection(end_result, op1, op2);
  277.  
  278.     op1->doc_ids_array -= op1_number_of_hits - op1->number_of_hits;
  279.     op2->doc_ids_array -= op2_number_of_hits - op2->number_of_hits;
  280.     end_result->doc_ids_array -= end_result->number_of_hits;
  281.     op2->number_of_hits = end_result->number_of_hits;
  282.     s_free(op1->doc_ids_array);
  283.     if(end_result->number_of_hits > 0) {
  284.       op2->doc_ids_array = 
  285.         (doc_descr_struct *)
  286.           s_realloc(op2->doc_ids_array, 
  287.                     end_result->number_of_hits * doc_ids_array_size);
  288.       memcpy((char *)op2->doc_ids_array, 
  289.              (char *)end_result->doc_ids_array, 
  290.              end_result->number_of_hits * doc_ids_array_size);
  291.     }
  292.     else {
  293.       op2->number_of_hits = end_result->number_of_hits;
  294.       s_free(op2->doc_ids_array);
  295.     }
  296.     push(op2->word_id);
  297.   }
  298. }
  299.  
  300. void Difference(result, set1, set2)
  301.      search_result_struct *result;
  302.      search_result_struct *set1;
  303.      search_result_struct *set2;
  304. {
  305.   while((set1->number_of_hits != 0) &&
  306.         (set2->number_of_hits != 0)) {
  307.     if(set1->doc_ids_array->doc_id == set2->doc_ids_array->doc_id) {
  308.       --set1->number_of_hits; --set2->number_of_hits;
  309.       ++set1->doc_ids_array; ++set2->doc_ids_array;
  310.     }
  311.     else if(set1->doc_ids_array->doc_id < set2->doc_ids_array->doc_id) {
  312.       result->doc_ids_array->doc_id = set1->doc_ids_array->doc_id;
  313.       result->doc_ids_array->score = set1->doc_ids_array->score;
  314.       ++result->number_of_hits;
  315.       ++result->doc_ids_array;
  316.       --set1->number_of_hits;
  317.       ++set1->doc_ids_array;
  318.     }
  319.     else /* doc_id1 > doc_id2 */ {
  320.       --set2->number_of_hits;
  321.       ++set2->doc_ids_array;
  322.     }
  323.   }
  324.   if((set1->number_of_hits != 0) &&
  325.      (set2->number_of_hits == 0)) {
  326.     memcpy((char *)result->doc_ids_array, 
  327.            set1->doc_ids_array, 
  328.            set1->number_of_hits * sizeof(doc_descr_struct));
  329.     set1->doc_ids_array += set1->number_of_hits;
  330.     result->doc_ids_array += set1->number_of_hits;
  331.     result->number_of_hits += set1->number_of_hits;
  332.     set1->number_of_hits = 0;
  333.   }
  334. }
  335.  
  336. void Not_Operator( operand1, operand2)
  337.      long operand1;
  338.      long operand2;
  339. {
  340.   search_result_struct *op1, *op2;
  341.   long doc_score_size = sizeof(search_result_struct);
  342.   long doc_ids_array_size = sizeof(doc_descr_struct);
  343.   long op1_number_of_hits, op2_number_of_hits;
  344.   
  345.   op1 = &search_result_array[operand1];
  346.   op2 = &search_result_array[operand2];
  347.   op1_number_of_hits = op1->number_of_hits;
  348.   op2_number_of_hits = op2->number_of_hits;
  349.   
  350.   if(op1->number_of_hits == 0) {
  351.     end_result->number_of_hits = 0;
  352.     if(op1->doc_ids_array != NULL)
  353.       s_free(op1->doc_ids_array);
  354.     if(op2->doc_ids_array != NULL)
  355.       s_free(op2->doc_ids_array);
  356.     push(op1->word_id);
  357.   }
  358.   else if(op2->number_of_hits == 0) {
  359.     if(op2->doc_ids_array != NULL)
  360.       s_free(op2->doc_ids_array);
  361.     if(op1->number_of_hits > 0) {
  362.       end_result->doc_ids_array = 
  363.         (doc_descr_struct *)
  364.           s_realloc(end_result->doc_ids_array, 
  365.                     op1->number_of_hits * doc_ids_array_size);
  366.       memcpy((char *)end_result->doc_ids_array, 
  367.              (char *)op1->doc_ids_array, 
  368.              doc_ids_array_size * op1->number_of_hits + 1);
  369.     }
  370.     end_result->number_of_hits = op1->number_of_hits;
  371.     push(op1->word_id);
  372.   }
  373.   else if((op1->number_of_hits != 0) &&
  374.           (op2->number_of_hits != 0)) {
  375.     end_result->doc_ids_array = 
  376.       (doc_descr_struct *)
  377.         s_realloc(end_result->doc_ids_array,
  378.                  (op1->number_of_hits + op2->number_of_hits) * 
  379.                   doc_ids_array_size);
  380.     end_result->number_of_hits = 0;
  381.     
  382.     Difference(end_result, op1, op2);
  383.     
  384.     op1->doc_ids_array -= op1_number_of_hits - op1->number_of_hits;
  385.     op2->doc_ids_array -= op2_number_of_hits - op2->number_of_hits;
  386.     end_result->doc_ids_array -= end_result->number_of_hits;
  387.     op1->number_of_hits = end_result->number_of_hits;
  388.     s_free(op2->doc_ids_array);
  389.     if(end_result->number_of_hits > 0) {
  390.       op1->doc_ids_array = 
  391.         (doc_descr_struct *)
  392.           s_realloc(op1->doc_ids_array, 
  393.                     end_result->number_of_hits * doc_ids_array_size);
  394.       memcpy((char *)op1->doc_ids_array, 
  395.              (char *)end_result->doc_ids_array, 
  396.              end_result->number_of_hits * doc_ids_array_size);
  397.     }
  398.     else {
  399.       op1->number_of_hits = end_result->number_of_hits;
  400.       s_free(op2->doc_ids_array);
  401.     }
  402.     push(op1->word_id);
  403.   }
  404. }
  405.  
  406. boolean stackinitialized = false;
  407.  
  408. boolean boolean_operations(operator)
  409.      char *operator;
  410. {
  411.   long word_id1, word_id2;
  412. #ifndef WIN32
  413.   int i;
  414. #endif
  415.   
  416.   word_id1 = word_id2 = -1L;
  417.   
  418.   if (!stackinitialized) {
  419.     stackinit();
  420.     stackinitialized = true;
  421.   }
  422.   if (!strcmp(operator, "or")) {
  423.     if(stackempty())
  424.       word_id1 = -1L;
  425.     else word_id1 = pop();
  426.     if(stackempty())
  427.       word_id2 = -1L;
  428.     else word_id2 = pop();
  429.     if((word_id1 == -1) || (word_id2 == -1))
  430.       return(false);
  431.       /*waislog(WLOG_HIGH, WLOG_ERROR,
  432.               "boolean search failed, too few operands.\n");*/
  433.     else Or_Operator(word_id1, word_id2);
  434.   }
  435.   else if (!strcmp(operator, "and")) {
  436.     if(stackempty())
  437.       word_id1 = -1L;
  438.     else word_id1 = pop();
  439.     if(stackempty())
  440.       word_id2 = -1L;
  441.     else word_id2 = pop();
  442.     if((word_id1 == -1) || (word_id2 == -1))
  443.       return(false);
  444.       /*waislog(WLOG_HIGH, WLOG_ERROR,
  445.               "boolean search failed, too few operands.\n");*/
  446.     else And_Operator(word_id1, word_id2);
  447.   }
  448.   else if (!strcmp(operator, "not")) {
  449.     if(stackempty())
  450.       word_id1 = -1L;
  451.     else word_id1 = pop();
  452.     if(stackempty())
  453.       word_id2 = -1L;
  454.     else word_id2 = pop();
  455.     if((word_id1 == -1) || (word_id2 == -1))
  456.       return(false);
  457.       /*waislog(WLOG_HIGH, WLOG_ERROR,
  458.               "boolean search failed, too few operands.\n");*/
  459.     else Not_Operator(word_id2, word_id1);
  460.   }
  461. }
  462.  
  463. void save_word_id(word_id)
  464.      long word_id;
  465. {
  466.   if (!stackinitialized) {
  467.     stackinit();
  468.     stackinitialized = true;
  469.   }
  470.   if(end_result == NULL)
  471.     end_result = 
  472.       (search_result_struct *)s_malloc(sizeof(search_result_struct));
  473.   if(end_result->doc_ids_array == NULL)
  474.     end_result->doc_ids_array = 
  475.       (doc_descr_struct *)
  476.         s_malloc((search_result_array[word_id].number_of_hits + 1) *
  477.                  sizeof(doc_descr_struct));
  478.   else end_result->doc_ids_array = 
  479.       (doc_descr_struct *)
  480.         s_realloc(end_result->doc_ids_array, 
  481.                   (search_result_array[word_id].number_of_hits + 1) *
  482.                   sizeof(doc_descr_struct));
  483.   end_result->number_of_hits = search_result_array[word_id].number_of_hits;
  484.   if(search_result_array[word_id].doc_ids_array != NULL) 
  485.     memcpy((char*)end_result->doc_ids_array,
  486.            (char*)search_result_array[word_id].doc_ids_array,
  487.            search_result_array[word_id].number_of_hits * 
  488.            sizeof(doc_descr_struct));
  489.   push(word_id);
  490. }
  491.  
  492. long retriev_result(entries)
  493.      long entries;
  494. {
  495.   int doc_id, count;
  496.   long number_of_hits = 0;
  497.   
  498.   if((end_result != NULL) && (document_score_array != NULL))
  499.     for(count=0; count < end_result->number_of_hits; count++) {
  500.       doc_id = end_result->doc_ids_array[count].doc_id;
  501.       document_score_array[doc_id] = end_result->doc_ids_array[count].score;
  502.       ++number_of_hits;
  503.     }
  504.   number_of_qwords = 0;
  505.   stackinitialized = false;
  506.   if(end_result != NULL) {
  507.     if(end_result->doc_ids_array != NULL)
  508.       s_free(end_result->doc_ids_array);
  509.     s_free(end_result);
  510.   }
  511.   if(search_result_array != NULL)
  512.     s_free(search_result_array);
  513.   return(number_of_hits);
  514. } 
  515.