home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / t / toaster.zip / Compat / array.c < prev    next >
C/C++ Source or Header  |  1991-12-31  |  30KB  |  1,250 lines
  1. #include <stdio.h>
  2. #include <string.h>
  3. #ifdef sun
  4. #include <alloca.h>
  5. #endif
  6. #include "config.h"
  7. #include "lint.h"
  8. #include "interpret.h"
  9. #include "object.h"
  10. #include "wiz_list.h"
  11. #include "regexp.h"
  12.  
  13. #if defined(__GNUC__) && !defined(lint)
  14. #define INLINE inline
  15. #else
  16. #define INLINE
  17. #endif
  18.  
  19. /*
  20.  * This file contains functions used to manipulate arrays.
  21.  * Some of them are connected to efuns, and some are only used internally
  22.  * by the game driver.
  23.  */
  24.  
  25. extern int d_flag;
  26.  
  27. int num_arrays;
  28. int total_array_size;
  29.  
  30. /*
  31.  * Make an empty vector for everyone to use, never to be deallocated.
  32.  * It is cheaper to reuse it, than to use malloc() and allocate.
  33.  */
  34. struct vector null_vector = {
  35.     0,    /* size */
  36.     1    /* Ref count, which will ensure that it will never be deallocated */
  37. };
  38.  
  39. /*
  40.  * Allocate an array of size 'n'.
  41.  */
  42. struct vector *allocate_array(n)
  43.     int n;
  44. {
  45.     extern struct svalue const0;
  46.     int i;
  47.     struct vector *p;
  48.  
  49.     if (n < 0 || n > MAX_ARRAY_SIZE)
  50.     error("Illegal array size.\n");
  51.     if (n == 0) {
  52.         p = &null_vector;
  53.     p->ref++;
  54.     return p;
  55.     }
  56.     num_arrays++;
  57.     total_array_size += sizeof (struct vector) + sizeof (struct svalue) *
  58.     (n-1);
  59.     p = ALLOC_VECTOR(n);
  60.     p->ref = 1;
  61.     p->size = n;
  62.     p->user = current_object->user;
  63.     if (p->user)
  64.     p->user->size_array += n;
  65.     for (i=0; i<n; i++)
  66.     p->item[i] = const0;
  67.     return p;
  68. }
  69.  
  70. void free_vector(p)
  71.     struct vector *p;
  72. {
  73.     int i;
  74.     p->ref--;
  75.     if (p->ref > 0)
  76.     return;
  77. #ifdef DEBUG
  78.     if (p == &null_vector)
  79.     fatal("Tried to free the zero-size shared vector.\n");
  80. #endif
  81.     for (i=0; i<p->size; i++)
  82.     free_svalue(&p->item[i], "free_vector");
  83.     if (p->user)
  84.     p->user->size_array -= p->size;
  85.     num_arrays--;
  86.     total_array_size -= sizeof (struct vector) + sizeof (struct svalue) *
  87.     (p->size-1);
  88.     free((char *)p);
  89. }
  90.  
  91. struct vector *shrink_array(p, n)
  92.     struct vector *p;
  93.     int n;
  94. {
  95.     if (n <= p->size >> 1) {
  96.     struct vector *res;
  97.  
  98.     res = slice_array(p, 0, n-1);
  99.     free_vector(p);
  100.     return res;
  101.     }
  102.     total_array_size += sizeof (struct svalue) * (n - p->size);
  103.     if (p->user)
  104.     p->user->size_array += n - p->size;
  105.     p->size = n;
  106.     return p;
  107. }
  108.  
  109. struct vector *explode_string(str, del)
  110.     char *str, *del;
  111. {
  112.     char *p, *beg;
  113.     int num, len;
  114.     struct vector *ret;
  115.     char *buff;
  116.  
  117.     len = strlen(del);
  118.  
  119.     if (len == 0) {
  120.         char tmp[2];
  121.         tmp[1] = '\0';
  122.     ret = allocate_array(len = strlen(str));
  123.         for (num = 0; num < len; ++num)
  124.         {
  125.            tmp[0] = str[num];
  126.            ret->item[num].type = T_STRING;
  127.            ret->item[num].string_type = STRING_SHARED;
  128.            ret->item[num].u.string = make_shared_string(tmp);
  129.         }  
  130.     return ret;
  131.     }
  132.     /*
  133.      * Skip leading 'del' strings, if any.
  134.      */
  135.     while(strncmp(str, del, len) == 0) {
  136.     str += len;
  137.     if (str[0] == '\0')
  138.            return 0;
  139.     }
  140.     /*
  141.      * Find number of occurences of the delimiter 'del'.
  142.      */
  143.     for (p=str, num=0; *p;) {
  144.     if (strncmp(p, del, len) == 0) {
  145.         num++;
  146.         p += len;
  147.     } else
  148.         p += 1;
  149.     }
  150.     /*
  151.      * Compute number of array items. It is either number of delimiters,
  152.      * or, one more.
  153.      */
  154.     if (strlen(str) < len || strcmp(str + strlen(str) - len, del) != 0)
  155.     num++;
  156.     if (num == 0)
  157.        return allocate_array(0);
  158.     buff = xalloc(strlen(str) + 1);
  159.     ret = allocate_array(num);
  160.     for (p=str, beg = str, num=0; *p; ) {
  161.     if (strncmp(p, del, len) == 0) {
  162.         strncpy(buff, beg, p - beg);
  163.         buff[p-beg] = '\0';
  164.         if (num >= ret->size)
  165.         fatal("Too big index in explode !\n");
  166.         /* free_svalue(&ret->item[num]); Not needed for new array */
  167.         ret->item[num].type = T_STRING;
  168.         ret->item[num].string_type = STRING_SHARED;
  169.         ret->item[num].u.string = make_shared_string(buff);
  170.         num++;
  171.         beg = p + len;
  172.         p = beg;
  173.     } else {
  174.         p += 1;
  175.     }
  176.     }
  177.     /* Copy last occurence, if there was not a 'del' at the end. */
  178.     if (*beg != '\0') {
  179.     free_svalue(&ret->item[num], "explode_string");
  180.     ret->item[num].type = T_STRING;
  181.     ret->item[num].string_type = STRING_SHARED;;
  182.     ret->item[num].u.string = make_shared_string(beg);
  183.     }
  184.     free(buff);
  185.     return ret;
  186. }
  187.  
  188. char *implode_string(arr, del)
  189.     struct vector *arr;
  190.     char *del;
  191. {
  192.     int size, i, num;
  193.     char *p, *q;
  194.  
  195.     check_for_destr(arr);
  196.     for (i=0, size = 0, num = 0; i < arr->size; i++) {
  197.     if (arr->item[i].type == T_STRING) {
  198.         size += strlen(arr->item[i].u.string);
  199.         num++;
  200.     }
  201.         if (arr->item[i].type == T_NUMBER) {
  202.             char buff[20];
  203.             sprintf(buff, "%d", arr->item[i].u.number);
  204.             num++;
  205.             size += strlen(buff);
  206.         }
  207.     }
  208.     if (num == 0)
  209.     return string_copy("");
  210.     p = xalloc(size + (num-1) * strlen(del) + 1);
  211.     q = p;
  212.     p[0] = '\0';
  213.     for (i=0, size=0, num=0; i < arr->size; i++) {
  214.     if (arr->item[i].type == T_STRING || arr->item[i].type == T_NUMBER) {
  215.         if (num > 0) {
  216.         strcpy(p, del);
  217.         p += strlen(del);
  218.         }
  219.             switch(arr->item[i].type)
  220.             { 
  221.                 case T_STRING:
  222.                 strcpy(p, arr->item[i].u.string);
  223.                 p += strlen(arr->item[i].u.string);
  224.                     break;
  225.                 case T_NUMBER:
  226.                 { 
  227.                     char buff[20];
  228.                     sprintf(buff, "%d", arr->item[i].u.number);
  229.                     strcpy(p, buff);
  230.                     p += strlen(buff);
  231.                 }                 
  232.             }
  233.         num++;
  234.     }
  235.     }
  236.     return q;
  237. }
  238.  
  239. struct vector *users() {
  240.     struct object *ob;
  241.     extern int num_player; /* set by comm1.c */
  242.     int i;
  243.     struct vector *ret;
  244.  
  245.     ret = allocate_array(num_player);
  246.     for (i = 0; i < num_player; i++) {
  247.     ret->item[i].type = T_OBJECT;
  248.     ret->item[i].u.ob = ob = get_interactive_object(num_player-i-1);
  249.     add_ref(ob, "users");
  250.     }
  251.     return ret;
  252. }
  253.  
  254. /*
  255.  * Check that an assignment to an array item is not cyclic.
  256.  */
  257. static void check_for_recursion(vec, v)
  258.     struct vector *vec, *v;
  259. {
  260.     register int i;
  261.     extern int eval_cost;
  262.  
  263.     if (vec->user)
  264.     vec->user->cost++;
  265.     eval_cost++;
  266.     if (v == vec)
  267.     error("Recursive asignment of vectors.\n");
  268.     for (i=0; i<v->size; i++) {
  269.     if (v->item[i].type == T_POINTER)
  270.         check_for_recursion(vec, v->item[i].u.vec);
  271.     }
  272. }
  273.  
  274. /*
  275.  * Slice of an array.
  276.  */
  277. struct vector *slice_array(p,from,to)
  278.     struct vector *p;
  279.     int from;
  280.     int to;
  281. {
  282.     struct vector *d;
  283.     int cnt;
  284.     
  285.     check_for_destr(p);
  286.     if (from < 0)
  287.        from = 0;
  288.     if (from >= p->size)  
  289.        return allocate_array(0);
  290.     if (to >= p->size) 
  291.        to = p->size-1;
  292.     if (to < from) 
  293.        return allocate_array(0);
  294.     
  295.     d = allocate_array(to-from+1);
  296.     for (cnt=from;cnt<=to;cnt++) 
  297.     assign_svalue_no_free (&d->item[cnt-from], &p->item[cnt]);
  298.     
  299.     return d;
  300. }
  301.  
  302. /* EFUN: filter_array
  303.    
  304.    Runs all elements of an array through ob->func()
  305.    and returns an array holding those elements that ob->func
  306.    returned 1 for.
  307.    */
  308. struct vector *filter (p, func, ob, extra)
  309.     struct vector *p;
  310.     char *func;
  311.     struct object *ob;
  312.     struct svalue *extra;
  313. {
  314.     struct vector *r;
  315.     struct svalue *v;
  316.     char *flags;
  317.     int cnt,res;
  318.     
  319.     res=0;
  320.     r=0;
  321.     if (!func || !ob || (ob->flags & O_DESTRUCTED)) 
  322.     {
  323.     if (d_flag) 
  324.         debug_message ("filter: invalid agument\n");
  325.     return 0;
  326.     }
  327.     if (p->size<1)
  328.         return allocate_array(0);
  329.  
  330.     flags=xalloc(p->size+1); 
  331.     for (cnt=0;cnt<p->size;cnt++) 
  332.     {
  333.     flags[cnt]=0;
  334.     push_svalue(&p->item[cnt]);
  335.     if (extra)   
  336.     {
  337.         push_svalue(extra);
  338.         v = apply (func, ob, 2);
  339.     } 
  340.     else 
  341.         v = apply (func, ob, 1);
  342.     if (v && v->type==T_NUMBER && v->u.number) 
  343.         {
  344.         flags[cnt]=1; 
  345.             res++; 
  346.     }
  347.     }
  348.     r = allocate_array(res);
  349.     if (res) 
  350.     {
  351.     for (cnt = res = 0; (res < r->size) && (cnt < p->size); cnt++) 
  352.     {
  353.         if (flags[cnt]) 
  354.         assign_svalue_no_free (&r->item[res++], &p->item[cnt]);
  355.     }
  356.     }
  357.     free(flags);
  358.     return r;
  359. }
  360.  
  361. /* Unique maker
  362.    
  363.    These routines takes an array of objects and calls the function 'func'
  364.    in them. The return values are used to decide which of the objects are
  365.    unique. Then an array on the below form are returned:
  366.    
  367.    ({
  368.    ({Same1:1, Same1:2, Same1:3, .... Same1:N }),
  369.    ({Same2:1, Same2:2, Same2:3, .... Same2:N }),
  370.    ({Same3:1, Same3:2, Same3:3, .... Same3:N }),
  371.    ....
  372.    ....
  373.    ({SameM:1, SameM:2, SameM:3, .... SameM:N }),
  374.    })
  375.    i.e an array of arrays consisting of lists of objectpointers
  376.     if (!arg1 || !arg2) return 0;
  377.    to all the nonunique objects for each unique set of objects.
  378.    
  379.    The basic purpose of this routine is to speed up the preparing of the
  380.    array used for describing.
  381.    
  382.    */
  383.  
  384. struct unique
  385. {
  386.     int count;
  387.     struct svalue *val;
  388.     struct svalue mark;
  389.     struct unique *same;
  390.     struct unique *next;
  391. };
  392.  
  393. static int sameval(arg1,arg2)
  394.     struct svalue *arg1;
  395.     struct svalue *arg2;
  396. {
  397.     if (arg1->type == T_NUMBER && arg2->type == T_NUMBER) {
  398.     return arg1->u.number == arg2->u.number;
  399.     } else if (arg1->type == T_POINTER && arg2->type == T_POINTER) {
  400.     return arg1->u.vec == arg2->u.vec;
  401.     } else if (arg1->type == T_STRING && arg2->type == T_STRING) {
  402.     return !strcmp(arg1->u.string, arg2->u.string);
  403.     } else if (arg1->type == T_OBJECT && arg2->type == T_OBJECT) {
  404.     return arg1->u.ob == arg2->u.ob;
  405.     } else
  406.     return 0;
  407. }
  408.  
  409.  
  410. static int put_in(ulist,marker,elem)
  411.     struct unique **ulist;
  412.     struct svalue *marker;
  413.     struct svalue *elem;
  414. {
  415.     struct unique *llink,*slink,*tlink;
  416.     int cnt,fixed;
  417.     
  418.     llink= *ulist;
  419.     cnt=0; fixed=0;
  420.     while (llink) {
  421.     if ((!fixed) && (sameval(marker,&(llink->mark)))) {
  422.         for (tlink=llink;tlink->same;tlink=tlink->same) (tlink->count)++;
  423.         (tlink->count)++;
  424.         slink = (struct unique *) xalloc(sizeof(struct unique));
  425.         slink->count = 1;
  426.         assign_svalue_no_free(&slink->mark,marker);
  427.         slink->val = elem;
  428.         slink->same = 0;
  429.         slink->next = 0;
  430.         tlink->same = slink;
  431.         fixed=1; /* We want the size of the list so do not break here */
  432.     }
  433.     llink=llink->next; cnt++;
  434.     }
  435.     if (fixed) return cnt;
  436.     llink = (struct unique *) xalloc(sizeof(struct unique));
  437.     llink->count = 1;
  438.     assign_svalue_no_free(&llink->mark,marker);
  439.     llink->val = elem;
  440.     llink->same = 0;
  441.     llink->next = *ulist;
  442.     *ulist = llink;
  443.     return cnt+1;
  444. }
  445.  
  446.  
  447. struct vector *
  448. make_unique(arr,func,skipnum)
  449.     struct vector *arr;
  450.     char *func;
  451.     struct svalue *skipnum;
  452. {
  453.     struct svalue *v;
  454.     struct vector *res,*ret;
  455.     struct unique *head,*nxt,*nxt2;
  456.     
  457.     int cnt,ant,cnt2;
  458.     
  459.     if (arr->size < 1)
  460.        return allocate_array(0);
  461.  
  462.     head = 0; ant=0; arr->ref++;
  463.     for(cnt=0;cnt<arr->size;cnt++) if (arr->item[cnt].type == T_OBJECT) {
  464.     v = apply(func,arr->item[cnt].u.ob,0);
  465.     if ((!v) || (v->type!=skipnum->type) || !sameval(v,skipnum)) 
  466.         if (v) ant=put_in(&head,v,&(arr->item[cnt]));
  467.     }
  468.     arr->ref--;
  469.  
  470.     ret = allocate_array(ant);
  471.     
  472.     for (cnt=ant-1;cnt>=0;cnt--) { /* Reverse to compensate put_in */
  473.     ret->item[cnt].type = T_POINTER;
  474.     ret->item[cnt].u.vec = res = allocate_array(head->count);
  475.     nxt2 = head;
  476.     head = head->next;
  477.     cnt2 = 0;
  478.     while (nxt2) {
  479.         assign_svalue_no_free (&res->item[cnt2++], nxt2->val);
  480.         free_svalue(&nxt2->mark, "make_unique");
  481.         nxt = nxt2->same;
  482.         free((char *) nxt2);
  483.         nxt2 = nxt;
  484.     }
  485.     if (!head) 
  486.         break; /* It shouldn't but, to avoid skydive just in case */
  487.     }
  488.     return ret;
  489. }
  490.  
  491. /*
  492.  * End of Unique maker
  493.  *************************
  494.  */
  495.  
  496. int equal_svalue(a, b)
  497. struct svalue *a, *b;
  498. {
  499.    if (a->type != b->type) return 0;
  500.    switch(a->type)
  501.    {
  502.       case T_NUMBER:
  503.          return a->u.number == b->u.number;
  504.       case T_OBJECT:
  505.          return a->u.ob == b->u.ob;
  506.       case T_POINTER:
  507.          return a->u.vec == b->u.vec;
  508.       case T_STRING:
  509.          return strcmp(a->u.string, b->u.string) == 0;
  510.    }
  511.   return 0;
  512. }
  513.  
  514. /*
  515.  * Returns all elements in p not in r.
  516.  */
  517. #ifdef COMPAT_MODE
  518. struct vector *subtract_array(p, r)
  519. struct vector *p;
  520. struct svalue *r;
  521. {
  522.    int i, size = 0;
  523.    struct vector *new, *tmp;
  524.    char *marked;
  525.  
  526.    tmp = allocate_array(p->size);
  527.    if (r->type != T_POINTER) 
  528.    {
  529.       for (i=0; i<p->size; ++i) 
  530.       {
  531.          if (!equal_svalue(r, &p->item[i]))
  532.             assign_svalue(&tmp->item[size++], &p->item[i]);
  533.          else break;
  534.       }
  535.       for (++i; i<p->size; ++i)
  536.          assign_svalue(&tmp->item[size++], &p->item[i]);
  537.    }
  538.    else
  539.    {
  540.       int j;
  541.       marked = xalloc(r->u.vec->size);
  542.       bzero(marked, r->u.vec->size);
  543.       for (i = 0; i<p->size; ++i)
  544.       {
  545.          int flag;
  546.          flag = 0;
  547.          for (j=0; j<r->u.vec->size; ++j)
  548.             if (equal_svalue(&p->item[i], &r->u.vec->item[j]) && !marked[j])
  549.             {
  550.                flag = 1;
  551.                marked[j] = 1;
  552.                break;
  553.             }
  554.          if (!flag) assign_svalue(&tmp->item[size++], &p->item[i]);
  555.       }  
  556.       free(marked);
  557.    }
  558.    new = allocate_array(size);
  559.    for (i=0; i<size; ++i)
  560.       assign_svalue(&new->item[i], &tmp->item[i]);
  561.    free_vector(tmp);
  562.    return new;
  563. }
  564. #else
  565. struct vector *subtract_array(minuend, subtrahend)
  566. struct vector *minuend, *subtrahend;
  567. {
  568.     struct vector *order_alist PROT((struct vector *));
  569.     struct vector *vtmpp;
  570.     static struct vector vtmp = { 1, 1,
  571. #ifdef DEBUG
  572.     1,
  573. #endif
  574.     0,
  575.     { { T_POINTER } }
  576.     };
  577.     struct vector *difference;
  578.     struct svalue *source,*dest;
  579.     int i;
  580.  
  581.     vtmp.item[0].u.vec = subtrahend;
  582.     vtmpp = order_alist(&vtmp);
  583.     free_vector(subtrahend);
  584.     subtrahend = vtmpp->item[0].u.vec;
  585.     difference = allocate_array(minuend->size);
  586.     for (source = minuend->item, dest = difference->item, i = minuend->size;
  587.       i--; source++) {
  588.         extern struct svalue const0;
  589.  
  590.         int assoc PROT((struct svalue *key, struct vector *));
  591.     if (source->type == T_OBJECT && source->u.ob->flags & O_DESTRUCTED)
  592.         assign_svalue(source, &const0);
  593.     if ( assoc(source, subtrahend) < 0 )
  594.         assign_svalue_no_free(dest++, source);
  595.     }
  596.     free_vector(vtmpp);
  597.     return shrink_array(difference, dest-difference->item);
  598. }
  599. #endif
  600.  
  601. /* Concatenation of two arrays into one
  602.  */
  603. struct vector *add_array(p,r)
  604.     struct vector *p, *r;
  605. {
  606.     int cnt,res;
  607.     struct vector *d;
  608.     
  609.     check_for_destr(p); check_for_destr(r);
  610.     d = allocate_array(p->size+r->size);
  611.     res=0;
  612.     for (cnt=0;cnt<p->size;cnt++) {
  613.     assign_svalue_no_free (&d->item[res],&p->item[cnt]);
  614.     res++; 
  615.     }
  616.     for (cnt=0;cnt<r->size;cnt++) {
  617.     assign_svalue_no_free (&d->item[res],&r->item[cnt]);
  618.     res++; 
  619.     }
  620.     return d;
  621. }
  622.  
  623.  
  624.  
  625. /* Returns an array of all objects contained in 'ob'
  626.  */
  627. struct vector *all_inventory(ob)
  628.     struct object *ob;
  629. {
  630.     struct vector *d;
  631.     struct object *cur;
  632.     int cnt,res;
  633.     
  634.     cnt=0;
  635.     for (cur=ob->contains; cur; cur = cur->next_inv)
  636.     cnt++;
  637.     
  638.     d = allocate_array(cnt);
  639.     cur=ob->contains;
  640.     
  641.     for (res=0;res<cnt;res++) {
  642.     d->item[res].type=T_OBJECT;
  643.     d->item[res].u.ob = cur;
  644.     add_ref(cur,"all_inventory");
  645.     cur=cur->next_inv;
  646.     }
  647.     return d;
  648. }
  649.  
  650.  
  651. /* Runs all elements of an array through ob::func
  652.    and replaces each value in arr by the value returned by ob::func
  653.    */
  654. struct vector *map_array (arr, func, ob, extra)
  655.     struct vector *arr;
  656.     char *func;
  657.     struct object *ob;
  658.     struct svalue *extra;
  659. {
  660.     struct vector *r;
  661.     struct svalue *v;
  662.     int cnt;
  663.     
  664.     check_for_destr(arr);
  665.  
  666.     r = allocate_array(arr->size);
  667.     
  668.     for (cnt = 0; cnt < arr->size; cnt++)
  669.     {
  670.     if (ob->flags & O_DESTRUCTED)
  671.         error("object used by map_array destructed"); /* amylaar */
  672.     push_svalue(&arr->item[cnt]);
  673.  
  674.     if (extra)
  675.     {
  676.         push_svalue (extra);
  677.         v = apply(func, ob, 2);
  678.     }
  679.     else 
  680.     {
  681.         v = apply(func,ob,1);
  682.     }
  683.     if (v)
  684.         assign_svalue_no_free (&r->item[cnt], v);
  685.     }
  686.     return r;
  687. }
  688.  
  689. static INLINE int sort_array_cmp(func, ob, p1, p2)
  690.     char *func;
  691.     struct object *ob;
  692.     struct svalue *p1,*p2;
  693. {
  694.     struct svalue *d;
  695.  
  696.     if (ob->flags & O_DESTRUCTED)
  697.         error("object used by sort_array destructed");
  698.     push_svalue(p1);
  699.     push_svalue(p2);
  700.     d = apply(func, ob, 2);
  701.     if (!d) return 0;
  702.     if (d->type != T_NUMBER) {
  703.     /* Amylaar: we expect the object to return a number, and there is
  704.      *        no need to use free_svalue on numbers. If, however,
  705.      *        some stupid LPC-programmer returns a non-number, memory
  706.      *        might be lost unless we free the svalue
  707.      */
  708.     free_svalue(d, "sort_array_cmp");
  709.     return 1;
  710.     }
  711.     return d->u.number > 0;
  712. }
  713.  
  714. struct vector *sort_array(inlist, func, ob)
  715.     struct vector *inlist;
  716.     char *func;
  717.     struct object *ob;
  718. {
  719.     struct vector *outlist;
  720.     struct svalue *root, *inpnt;
  721.     int keynum, j;
  722.  
  723.     keynum = inlist->size;
  724.     root = inlist->item;
  725.     /* transform inlist->item[j] into a heap, starting at the top */
  726.     for(j=0,inpnt=root; j<keynum; j++,inpnt++) {
  727.         extern struct svalue const0;
  728.     int curix, parix;
  729.     struct svalue insval;
  730.  
  731.     /* propagate the new element up in the heap as much as necessary */
  732.     if (inpnt->type == T_OBJECT && inpnt->u.ob->flags & O_DESTRUCTED)
  733.         assign_svalue(inpnt, &const0);
  734.     insval = *inpnt;
  735.     for(curix = j; curix; curix=parix) {
  736.         parix = (curix-1)>>1;
  737.         if ( sort_array_cmp(func, ob, &root[parix], &root[curix] ) ) {
  738.         root[curix] = root[parix];
  739.         root[parix] = insval;
  740.         }
  741.     }
  742.     }
  743.     outlist = allocate_array(keynum);
  744.     for(j=0; j<keynum; j++) {
  745.     int curix;
  746.  
  747.     outlist->item[j] = *root;
  748.     for (curix=0; ; ) {
  749.         int child, child2;
  750.  
  751.         child = curix+curix+1;
  752.         child2 = child+1;
  753.         if (child2<keynum && root[child2].type != T_INVALID
  754.           && (root[child].type == T_INVALID ||
  755.         sort_array_cmp(func, ob, &root[child], &root[child2] )
  756.         ) )
  757.         {
  758.         child = child2;
  759.         }
  760.         if (child<keynum && root[child].type != T_INVALID) {
  761.         root[curix] = root[child];
  762.         curix = child;
  763.         } else break;
  764.     }
  765.     root[curix].type = T_INVALID;
  766.     }
  767.     free_vector(inlist);
  768.     return outlist;
  769. }
  770.  
  771. /* Turns a structured array of elements into a flat array of elements.
  772.    */
  773. static int num_elems(arr)
  774.     struct vector *arr;
  775. {
  776.     int cnt,il;
  777.  
  778.     check_for_destr(arr);
  779.     cnt = arr->size;
  780.  
  781.     for (il=0;il<arr->size;il++) 
  782.     if (arr->item[il].type == T_POINTER) 
  783.         cnt += num_elems(arr->item[il].u.vec) - 1;
  784.     return cnt;
  785. }
  786.  
  787. struct vector *flatten_array(arr)
  788.     struct vector *arr;
  789. {
  790.     int max, cnt, il, il2;
  791.     struct vector *res, *dres;
  792.     
  793.     check_for_destr(arr);
  794.     if (arr->size < 1) 
  795.        return allocate_array(0);
  796.  
  797.     max = num_elems(arr);
  798.  
  799.     if (arr->size == max)
  800.     return arr;
  801.  
  802.     if (max == 0)         /* In the case arr is an array of empty arrays */
  803.        return allocate_array(0);
  804.  
  805.     res = allocate_array(max); 
  806.  
  807.     for (cnt = 0 , il = 0; il < arr->size; il++)
  808.     if (arr->item[il].type != T_POINTER) 
  809.         assign_svalue(&res->item[cnt++],&arr->item[il]);
  810.     else {
  811.         dres = flatten_array(arr->item[il].u.vec);
  812.         for (il2=0;il2<dres->size;il2++)
  813.         assign_svalue(&res->item[cnt++],&dres->item[il2]);
  814.         free_vector(dres);
  815.     }
  816.     
  817.     return res;
  818. }
  819. /*
  820.  * deep_inventory()
  821.  *
  822.  * This function returns the recursive inventory of an object. The returned 
  823.  * array of objects is flat, ie there is no structure reflecting the 
  824.  * internal containment relations.
  825.  *
  826.  */
  827. struct vector *deep_inventory(ob, take_top)
  828.     struct object    *ob;
  829.     int            take_top;
  830. {
  831.     struct vector    *dinv, *ainv, *sinv, *tinv;
  832.     int            il;
  833.  
  834.     ainv = all_inventory(ob);
  835.     if (take_top)
  836.     {
  837.     sinv = allocate_array(1);
  838.     sinv->item[0].type = T_OBJECT;
  839.     add_ref(ob,"deep_inventory");
  840.     sinv->item[0].u.ob = ob;
  841.     dinv = add_array(sinv, ainv);
  842.     free_vector(sinv);
  843.     free_vector(ainv);
  844.     ainv = dinv;
  845.     }
  846.     sinv = ainv;
  847.     for (il = take_top ? 1 : 0 ; il < ainv->size ; il++)
  848.     {
  849.     if (ainv->item[il].u.ob->contains)
  850.     {
  851.         dinv = deep_inventory(ainv->item[il].u.ob,0);
  852.         tinv = add_array(sinv, dinv);
  853.         if (sinv != ainv)
  854.         free_vector(sinv);
  855.         sinv = tinv;
  856.         free_vector(dinv);
  857.     }
  858.     }
  859.     if (ainv != sinv)
  860.     free_vector(ainv);
  861.     return sinv;
  862. }
  863.  
  864.  
  865. /* sum_array, processes each element in the array together with the
  866.               results from the previous element. Starting value is 0.
  867.           Note! This routine allocates a struct svalue which it returns.
  868.           This value should be pushed to the stack and then freed.
  869.    */
  870. struct svalue *sum_array (arr, func, ob, extra)
  871.     struct vector *arr;
  872.     char *func;
  873.     struct object *ob;
  874.     struct svalue *extra;
  875. {
  876.     struct svalue *ret, v;
  877.  
  878.     int cnt;
  879.  
  880.     check_for_destr(arr);
  881.     v.type = T_NUMBER;
  882.     v.u.number = 0;
  883.  
  884.     for (cnt=0;cnt<arr->size;cnt++) {
  885.     push_svalue(&arr->item[cnt]);
  886.     push_svalue(&v);
  887.     if (extra) {
  888.         push_svalue (extra);
  889.         ret = apply(func, ob, 3);
  890.     } else {
  891.         ret = apply(func,ob,2);
  892.     }
  893.     if (ret)
  894.         v = *ret;
  895.     }
  896.  
  897.     ret = (struct svalue *) xalloc(sizeof(struct svalue));
  898.     *ret = v;
  899.  
  900.     return ret;
  901. }
  902.  
  903.  
  904. static INLINE int alist_cmp(p1, p2)
  905.     struct svalue *p1,*p2;
  906. {
  907.     register int d;
  908.  
  909.     if (d = p1->u.number - p2->u.number) return d;
  910.     if (d = p1->type - p2->type) return d;
  911.     return 0;
  912. }
  913.  
  914. struct vector *order_alist(inlist)
  915.     struct vector *inlist;
  916. {
  917.     struct vector *outlist;
  918.     struct svalue *inlists, *outlists, *root, *inpnt, *insval;
  919.     int listnum, keynum, i, j;
  920.  
  921.     listnum = inlist->size;
  922.     inlists = inlist->item;
  923.     keynum = inlists[0].u.vec->size;
  924.     root = inlists[0].u.vec->item;
  925.     /* transform inlists[i].u.vec->item[j] into a heap, starting at the top */
  926.     insval = (struct svalue*)xalloc(sizeof(struct svalue[1])*listnum);
  927.     for(j=0,inpnt=root; j<keynum; j++,inpnt++) {
  928.     int curix, parix;
  929.  
  930.     /* make sure that strings can be compared by their pointer */
  931.     if (inpnt->type == T_STRING && inpnt->string_type != STRING_SHARED) {
  932.         char *str = make_shared_string(inpnt->u.string);
  933.         free_svalue(inpnt, "");
  934.         inpnt->type = T_STRING;
  935.         inpnt->string_type = STRING_SHARED;
  936.         inpnt->u.string = str;
  937.     }
  938.     /* propagate the new element up in the heap as much as necessary */
  939.     for (i=0; i<listnum; i++) {
  940.         insval[i] = inlists[i].u.vec->item[j];
  941.         /* but first ensure that it contains no destructed object */
  942.         if (insval[i].type == T_OBJECT
  943.           && insval[i].u.ob->flags & O_DESTRUCTED) {
  944.                 extern struct svalue const0;
  945.  
  946.         free_object(insval[i].u.ob, "order_alist");
  947.             inlists[i].u.vec->item[j] = insval[i] = const0;
  948.         }
  949.     }
  950.     for(curix = j; curix; curix=parix) {
  951.         parix = (curix-1)>>1;
  952.         if ( alist_cmp(&root[parix], &root[curix]) > 0 ) {
  953.         for (i=0; i<listnum; i++) {
  954.             inlists[i].u.vec->item[curix] =
  955.               inlists[i].u.vec->item[parix];
  956.             inlists[i].u.vec->item[parix] = insval[i];
  957.         }
  958.         }
  959.     }
  960.     }
  961.     free((char*)insval);
  962.     outlist = allocate_array(listnum);
  963.     outlists = outlist->item;
  964.     for (i=0; i<listnum; i++) {
  965.     outlists[i].type  = T_POINTER;
  966.     outlists[i].u.vec = allocate_array(keynum);
  967.     }
  968.     for(j=0; j<keynum; j++) {
  969.     int curix;
  970.  
  971.     for (i=0;  i<listnum; i++) {
  972.         outlists[i].u.vec->item[j] = inlists[i].u.vec->item[0];
  973.     }
  974.     for (curix=0; ; ) {
  975.         int child, child2;
  976.  
  977.         child = curix+curix+1;
  978.         child2 = child+1;
  979.         if (child2<keynum && root[child2].type != T_INVALID
  980.           && (root[child].type == T_INVALID ||
  981.         alist_cmp(&root[child], &root[child2]) > 0))
  982.         {
  983.         child = child2;
  984.         }
  985.         if (child<keynum && root[child].type != T_INVALID) {
  986.         for (i=0; i<listnum; i++) {
  987.             inlists[i].u.vec->item[curix] =
  988.               inlists[i].u.vec->item[child];
  989.         }
  990.         curix = child;
  991.         } else break;
  992.     }
  993.     for (i=0; i<listnum; i++) {
  994.         inlists[i].u.vec->item[curix].type = T_INVALID;
  995.     }
  996.     }
  997.     return outlist;
  998. }
  999.  
  1000. static int search_alist(key, keylist)
  1001.     struct svalue *key;
  1002.     struct vector *keylist;
  1003. {
  1004.     int i, o, d;
  1005.  
  1006.     if (!keylist->size) return 0;
  1007.     i = (keylist->size) >> 1;
  1008.     o = (i+2) >> 1;
  1009.     for (;;) {
  1010.     d = alist_cmp(key, &keylist->item[i]);
  1011.     if (d<0) {
  1012.         i -= o;
  1013.         if (i<0) {
  1014.         i = 0;
  1015.         }
  1016.     } else if (d>0) {
  1017.         i += o;
  1018.         if (i >= keylist->size) {
  1019.             i = keylist->size-1;
  1020.         }
  1021.     } else {
  1022.         return i;
  1023.     }
  1024.     if (o<=1) {
  1025.         if (alist_cmp(key, &keylist->item[i]) > 0) return i+1;
  1026.         return i;
  1027.     }
  1028.     o = (o+1) >> 1;
  1029.     }
  1030. }
  1031.  
  1032. #define    STRING_REFS(str)    (*(short *)((char *) (str) - sizeof(short)))
  1033.  
  1034. struct svalue *insert_alist(key, key_data, list)
  1035. struct svalue *key, *key_data;
  1036. struct vector *list;
  1037. {
  1038.     static struct svalue stmp;
  1039.     int i,j,ix;
  1040.     int keynum;
  1041.  
  1042.     if (key->type == T_STRING && key->string_type != STRING_SHARED) {
  1043.     static struct svalue stmp2 = { T_STRING, STRING_SHARED };
  1044.  
  1045.     stmp2.u.string = make_shared_string(key->u.string);
  1046.     STRING_REFS(stmp2.u.string)--;
  1047.     /* a reference count will be added again when copied
  1048.        to it's place in the alist */
  1049.     key = &stmp2;
  1050.     }
  1051.     keynum = list->item[0].u.vec->size;
  1052.     ix = search_alist(key,list->item[0].u.vec);
  1053.     if (key_data == 0) {
  1054.      stmp.type = T_NUMBER;
  1055.      stmp.u.number = ix;
  1056.          return &stmp;
  1057.     }
  1058.     stmp.type = T_POINTER;
  1059.     stmp.u.vec = allocate_array(list->size);
  1060.     for (i=0; i < list->size; i++) {
  1061.     struct vector *vtmp;
  1062.  
  1063.         if (ix == keynum || alist_cmp(key, &list->item[0].u.vec->item[ix]) ) {
  1064.             struct svalue *pstmp = list->item[i].u.vec->item;
  1065.             struct vector *delete_elements();
  1066.         vtmp = allocate_array(keynum+1);
  1067.             for (j=0; j < ix; j++) {
  1068.                assign_svalue_no_free(&vtmp->item[j], pstmp++);
  1069.             }
  1070.             assign_svalue_no_free(&vtmp->item[ix], i ? &key_data[i] : key);
  1071.             for (j=ix+1; j <= keynum; j++) {
  1072.                assign_svalue_no_free(&vtmp->item[j], pstmp++);
  1073.             }
  1074.     } else {
  1075.         vtmp = slice_array(list->item[i].u.vec, 0, keynum-1);
  1076.         if (i)
  1077.             assign_svalue(&vtmp->item[ix], &key_data[i]);
  1078.     }
  1079.     stmp.u.vec->item[i].type=T_POINTER;
  1080.     stmp.u.vec->item[i].u.vec=vtmp;
  1081.     }
  1082.     return &stmp;
  1083. }
  1084.  
  1085.  
  1086. int assoc(key, list)
  1087.     struct svalue *key;
  1088.     struct vector *list;
  1089. {
  1090.     int i;
  1091.     extern char* findstring PROT((char*));
  1092.  
  1093.     if (key->type == T_STRING && key->string_type != STRING_SHARED) {
  1094.         static struct svalue stmp = { T_STRING, STRING_SHARED };
  1095.  
  1096.         stmp.u.string = findstring(key->u.string);
  1097.         if (!stmp.u.string) return -1;
  1098.         key = &stmp;
  1099.     }
  1100.     i = search_alist(key, list);
  1101.     if (i == list->size || alist_cmp(key, &list->item[i]))
  1102.         i = -1;
  1103.     return i;
  1104. }
  1105.  
  1106. struct vector *intersect_alist(a1, a2)
  1107.     struct vector *a1,*a2;
  1108. {
  1109.     struct vector *a3;
  1110.     int d, l, i1, i2, a1s, a2s;
  1111.  
  1112.     a1s = a1->size;
  1113.     a2s = a2->size;
  1114.     a3 = allocate_array( a1s < a2s ? a1s : a2s);
  1115.     for (i1=i2=l=0; i1 < a1s && i2 < a2s; ) {
  1116.     d = alist_cmp(&a1->item[i1], &a2->item[i2]);
  1117.     if (d<0)
  1118.         i1++;
  1119.     else if (d>0)
  1120.         i2++;
  1121.     else {
  1122.         assign_svalue_no_free(&a3->item[l++], &a2->item[i1++,i2++]);
  1123.     }
  1124.     }
  1125.     return shrink_array(a3, l);
  1126. }
  1127.  
  1128. struct vector *symmetric_difference_alist(a1, a2)
  1129.     struct vector *a1,*a2;
  1130. {
  1131.     struct vector *a3;
  1132.     int d, l, i1, i2, a1s, a2s;
  1133.  
  1134.     a1s = a1->size;
  1135.     a2s = a2->size;
  1136.     a3 = allocate_array( a1s + a2s );
  1137.     for (i1=i2=l=0; i1 < a1s && i2 < a2s; ) {
  1138.     d = alist_cmp(&a1->item[i1], &a2->item[i2]);
  1139.     if (d<0)
  1140.         assign_svalue_no_free(&a3->item[l++], &a1->item[i1++]);
  1141.     else if (d>0)
  1142.         assign_svalue_no_free(&a3->item[l++], &a2->item[i2++]);
  1143.     else {
  1144.         i1++;
  1145.         i2++;
  1146.     }
  1147.     }
  1148.     while (i1 < a1s )
  1149.         assign_svalue_no_free(&a3->item[l++], &a1->item[i1++]);
  1150.     while (i2 < a2s )
  1151.         assign_svalue_no_free(&a3->item[l++], &a2->item[i2++]);
  1152.     return shrink_array(a3, l);
  1153. }
  1154.  
  1155. struct vector *intersect_array(a1, a2)
  1156.     struct vector *a1,*a2;
  1157. {
  1158.     struct vector *order_alist PROT((struct vector *));
  1159.     struct vector *vtmpp1,*vtmpp2,*vtmpp3;
  1160.     static struct vector vtmp = { 1, 1,
  1161. #ifdef DEBUG
  1162.     1,
  1163. #endif
  1164.     0,
  1165.     { { T_POINTER } }
  1166.     };
  1167.  
  1168.     if (a1->ref > 1) {
  1169.     a1->ref--;
  1170.     a1 = slice_array(a1, 0, a1->size-1);
  1171.     }
  1172.     vtmp.item[0].u.vec = a1;
  1173.     vtmpp1 = order_alist(&vtmp);
  1174.     free_vector(vtmp.item[0].u.vec);
  1175.     if (a2->ref > 1) {
  1176.     a2->ref--;
  1177.     a2 = slice_array(a2, 0, a2->size-1);
  1178.     }
  1179.     vtmp.item[0].u.vec = a2;
  1180.     vtmpp2 = order_alist(&vtmp);
  1181.     free_vector(vtmp.item[0].u.vec);
  1182.     vtmpp3 = intersect_alist(vtmpp1->item[0].u.vec, vtmpp2->item[0].u.vec);
  1183.     free_vector(vtmpp1);
  1184.     free_vector(vtmpp2);
  1185.     return vtmpp3;
  1186. }
  1187.  
  1188. struct vector *match_regexp(v, pattern)
  1189.     struct vector *v;
  1190.     char *pattern;
  1191. {
  1192.     struct regexp *reg;
  1193.     char *res;
  1194.     int i, num_match;
  1195.     struct vector *ret;
  1196.     extern int eval_cost;
  1197.  
  1198.     if (v->size == 0)
  1199.     return allocate_array(0);
  1200.     reg = regcomp(pattern, 0);
  1201.     if (reg == 0)
  1202.     return 0;
  1203.     res = (char *)alloca(v->size);
  1204.     for (num_match=i=0; i < v->size; i++) {
  1205.     res[i] = 0;
  1206.     if (v->item[i].type != T_STRING)
  1207.         continue;
  1208.     eval_cost++;
  1209.     if (regexec(reg, v->item[i].u.string) == 0)
  1210.         continue;
  1211.     res[i] = 1;
  1212.     num_match++;
  1213.     }
  1214.     ret = allocate_array(num_match);
  1215.     for (num_match=i=0; i < v->size; i++) {
  1216.     if (res[i] == 0)
  1217.         continue;
  1218.     assign_svalue_no_free(&ret->item[num_match], &v->item[i]);
  1219.     num_match++;
  1220.     }
  1221.     free((char *)reg);
  1222.     return ret;
  1223. }
  1224.  
  1225. struct vector *delete_elements(v, n1, n2)
  1226. struct vector *v;
  1227. int n1, n2;
  1228. {
  1229.    int i;
  1230.    struct vector *n;
  1231.  
  1232.    check_for_destr(v);
  1233.    if (n1 > n2) 
  1234.    {
  1235.       i = n2; 
  1236.       n2 = n1; 
  1237.       n1 = i;
  1238.    }
  1239.    if (n1 < 0 || n2 < 0 || n1 >= v->size)
  1240.       error("Invalid index\n");
  1241.    if (n2 >= v->size)
  1242.       n2 = v->size - 1;
  1243.    n = allocate_array(v->size - (n2 - n1) - 1);
  1244.    for (i=0; i < n1; i++)
  1245.       assign_svalue(&n->item[i], &v->item[i]);
  1246.    for ( ; i < n->size; i++)
  1247.       assign_svalue(&n->item[i], &v->item[i + (n2 - n1) + 1]);
  1248.    return n;
  1249. }
  1250.