home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v941.tgz / icon.v941src.tar / icon.v941src / src / runtime / oset.r < prev    next >
Text File  |  2001-12-12  |  9KB  |  300 lines
  1. /*
  2.  * File: oset.r
  3.  *  Contents: compl, diff, inter, union
  4.  */
  5.  
  6. "~x - complement cset x."
  7.  
  8. operator{1} ~ compl(x)
  9.    /*
  10.     * x must be a cset.
  11.     */
  12.    if !cnv:tmp_cset(x) then
  13.       runerr(104, x)
  14.  
  15.    abstract {
  16.       return cset
  17.       }
  18.    body {
  19.       register int i;
  20.       struct b_cset *cp, *cpx;
  21.  
  22.       /*
  23.        * Allocate a new cset and then copy each cset word from x
  24.        *  into the new cset words, complementing each bit.
  25.        */
  26.       Protect(cp = alccset(), runerr(0));
  27.       cpx = (struct b_cset *)BlkLoc(x);      /* must come after alccset() */
  28.       for (i = 0; i < CsetSize; i++)
  29.           cp->bits[i] = ~cpx->bits[i];
  30.       return cset(cp);
  31.       }
  32. end
  33.  
  34.  
  35. "x -- y - difference of csets x and y or of sets x and y."
  36.  
  37. operator{1} -- diff(x,y)
  38.    if is:set(x) && is:set(y) then {
  39.       abstract {
  40.          return type(x)
  41.          }
  42.       body {
  43.      int res;
  44.          register int i;
  45.          register word slotnum;
  46.          tended union block *srcp, *tstp, *dstp;
  47.          tended struct b_slots *seg;
  48.          tended struct b_selem *ep;
  49.          struct b_selem *np;
  50.          union block **hook;
  51.  
  52.          /*
  53.           * Make a new set based on the size of x.
  54.           */
  55.          dstp = hmake(T_Set, (word)0, BlkLoc(x)->set.size);
  56.          if (dstp == NULL)
  57.             runerr(0);
  58.          /*
  59.           * For each element in set x if it is not in set y
  60.           *  copy it directly into the result set.
  61.       *
  62.       * np always has a new element ready for use.  We get one in advance,
  63.       *  and stay one ahead, because hook can't be tended.
  64.           */
  65.          srcp = BlkLoc(x);
  66.          tstp = BlkLoc(y);
  67.          Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  68.  
  69.          for (i = 0; i < HSegs && (seg = srcp->set.hdir[i]) != NULL; i++)
  70.             for (slotnum = segsize[i] - 1; slotnum >= 0; slotnum--) {
  71.                ep = (struct b_selem *)seg->hslots[slotnum];
  72.                while (ep != NULL) {
  73.                   memb(tstp, &ep->setmem, ep->hashnum, &res);
  74.                   if (res == 0) {
  75.                      hook = memb(dstp, &ep->setmem, ep->hashnum, &res);
  76.              np->setmem = ep->setmem;
  77.              np->hashnum = ep->hashnum;
  78.                      addmem(&dstp->set, np, hook);
  79.                      Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  80.                      }
  81.                   ep = (struct b_selem *)ep->clink;
  82.                   }
  83.                }
  84.      deallocate((union block *)np);
  85.          if (TooSparse(dstp))
  86.             hshrink(dstp);
  87.          Desc_EVValD(dstp, E_Screate, D_Set);
  88.          return set(dstp);
  89.          }
  90.       }
  91.    else {
  92.       if !cnv:tmp_cset(x) then
  93.          runerr(120, x)
  94.       if !cnv:tmp_cset(y) then
  95.          runerr(120, y)
  96.       abstract {
  97.          return cset
  98.          }
  99.       /*
  100.        * Allocate a new cset and in each word of it, compute the value
  101.        *  of the bitwise difference of the corresponding words in the
  102.        *  Arg1 and Arg2 csets.
  103.        */
  104.       body {
  105.          struct b_cset *cp, *cpx, *cpy;
  106.          register int i;
  107.  
  108.          Protect(cp = alccset(), runerr(0));
  109.          cpx = (struct b_cset *)BlkLoc(x);  /* must come after alccset() */
  110.          cpy = (struct b_cset *)BlkLoc(y);  /* must come after alccset() */
  111.          for (i = 0; i < CsetSize; i++)
  112.             cp->bits[i] = cpx->bits[i] & ~cpy->bits[i];
  113.          return cset(cp);
  114.          }
  115.       }
  116. end
  117.  
  118.  
  119. "x ** y - intersection of csets x and y or of sets x and y."
  120.  
  121. operator{1} ** inter(x,y)
  122.    if is:set(x) && is:set(y) then {
  123.       abstract {
  124.          return new set(store[type(x).set_elem] ** store[type(y).set_elem])
  125.          }
  126.       body {
  127.      int res;
  128.          register int i;
  129.          register word slotnum;
  130.          tended union block *srcp, *tstp, *dstp;
  131.          tended struct b_slots *seg;
  132.          tended struct b_selem *ep;
  133.          struct b_selem *np;
  134.          union block **hook;
  135.  
  136.          /*
  137.           * Make a new set the size of the smaller argument set.
  138.           */
  139.          dstp = hmake(T_Set, (word)0,
  140.             Min(BlkLoc(x)->set.size, BlkLoc(y)->set.size));
  141.          if (dstp == NULL)
  142.             runerr(0);
  143.          /*
  144.           * Using the smaller of the two sets as the source
  145.           *  copy directly into the result each of its elements
  146.           *  that are also members of the other set.
  147.       *
  148.       * np always has a new element ready for use.  We get one in advance,
  149.       *  and stay one ahead, because hook can't be tended.
  150.           */
  151.          if (BlkLoc(x)->set.size <= BlkLoc(y)->set.size) {
  152.             srcp = BlkLoc(x);
  153.             tstp = BlkLoc(y);
  154.             }
  155.          else {
  156.             srcp = BlkLoc(y);
  157.             tstp = BlkLoc(x);
  158.             }
  159.          Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  160.          for (i = 0; i < HSegs && (seg = srcp->set.hdir[i]) != NULL; i++)
  161.             for (slotnum = segsize[i] - 1; slotnum >= 0; slotnum--) {
  162.                ep = (struct b_selem *)seg->hslots[slotnum];
  163.                while (ep != NULL) {
  164.                   memb(tstp, &ep->setmem, ep->hashnum, &res);
  165.                   if (res != 0) {
  166.                      hook = memb(dstp, &ep->setmem, ep->hashnum, &res);
  167.              np->setmem = ep->setmem;
  168.              np->hashnum = ep->hashnum;
  169.                      addmem(&dstp->set, np, hook);
  170.                      Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  171.                      }
  172.                   ep = (struct b_selem *)ep->clink;
  173.                   }
  174.                }
  175.      deallocate((union block *)np);
  176.          if (TooSparse(dstp))
  177.             hshrink(dstp);
  178.          Desc_EVValD(dstp, E_Screate, D_Set);
  179.          return set(dstp);
  180.          }
  181.       }
  182.    else {
  183.  
  184.       if !cnv:tmp_cset(x) then
  185.          runerr(120, x)
  186.       if !cnv:tmp_cset(y) then
  187.          runerr(120, y)
  188.       abstract {
  189.          return cset
  190.          }
  191.  
  192.       /*
  193.        * Allocate a new cset and in each word of it, compute the value
  194.        *  of the bitwise intersection of the corresponding words in the
  195.        *  x and y csets.
  196.        */
  197.       body {
  198.          struct b_cset *cp, *cpx, *cpy;
  199.          register int i;
  200.  
  201.          Protect(cp = alccset(), runerr(0));
  202.          cpx = (struct b_cset *)BlkLoc(x);  /* must come after alccset() */
  203.          cpy = (struct b_cset *)BlkLoc(y);  /* must come after alccset() */
  204.          for (i = 0; i < CsetSize; i++) {
  205.             cp->bits[i] = cpx->bits[i] & cpy->bits[i];
  206.             }
  207.          return cset(cp);
  208.          }
  209.       }
  210. end
  211.  
  212.  
  213. "x ++ y - union of csets x and y or of sets x and y."
  214.  
  215. operator{1} ++ union(x,y)
  216.    if is:set(x) && is:set(y) then {
  217.       abstract {
  218.          return new set(store[type(x).set_elem] ++ store[type(y).set_elem])
  219.          }
  220.       body {
  221.      int res;
  222.      register int i;
  223.      register word slotnum;
  224.          struct descrip d;
  225.          tended union block *dstp;
  226.          tended struct b_slots *seg;
  227.          tended struct b_selem *ep;
  228.          struct b_selem *np;
  229.          union block **hook;
  230.  
  231.          /*
  232.           * Ensure that x is the larger set; if not, swap.
  233.           */
  234.          if (BlkLoc(y)->set.size > BlkLoc(x)->set.size) {
  235.         d = x;
  236.         x = y;
  237.         y = d;
  238.         }
  239.          /*
  240.           * Copy x and ensure there's room for *x + *y elements.
  241.           */
  242.          if (cpset(&x, &result, BlkLoc(x)->set.size + BlkLoc(y)->set.size)
  243.             == Error)
  244.             runerr(0);
  245.          /*
  246.           * Copy each element from y into the result, if not already there.
  247.       *
  248.       * np always has a new element ready for use.  We get one in advance,
  249.       *  and stay one ahead, because hook can't be tended.
  250.           */
  251.          dstp = BlkLoc(result);
  252.          Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  253.          for (i = 0; i < HSegs && (seg = BlkLoc(y)->set.hdir[i]) != NULL; i++)
  254.             for (slotnum = segsize[i] - 1; slotnum >= 0; slotnum--) {
  255.                ep = (struct b_selem *)seg->hslots[slotnum];
  256.                while (ep != NULL) {
  257.                   hook = memb(dstp, &ep->setmem, ep->hashnum, &res);
  258.                   if (res == 0) {
  259.              np->setmem = ep->setmem;
  260.              np->hashnum = ep->hashnum;
  261.                      addmem(&dstp->set, np, hook);
  262.                      Protect(np = alcselem(&nulldesc, (uword)0), runerr(0));
  263.                      }
  264.                   ep = (struct b_selem *)ep->clink;
  265.                   }
  266.                }
  267.      deallocate((union block *)np);
  268.          if (TooCrowded(dstp))        /* if the union got too big, enlarge */
  269.             hgrow(dstp);
  270.          return result;
  271.      }
  272.       }
  273.    else {
  274.       if !cnv:tmp_cset(x) then
  275.          runerr(120, x)
  276.       if !cnv:tmp_cset(y) then
  277.          runerr(120, y)
  278.       abstract {
  279.          return cset
  280.          }
  281.  
  282.       /*
  283.        * Allocate a new cset and in each word of it, compute the value
  284.        *  of the bitwise union of the corresponding words in the
  285.        *  x and y csets.
  286.        */
  287.       body {
  288.          struct b_cset *cp, *cpx, *cpy;
  289.          register int i;
  290.  
  291.          Protect(cp = alccset(), runerr(0));
  292.          cpx = (struct b_cset *)BlkLoc(x);  /* must come after alccset() */
  293.          cpy = (struct b_cset *)BlkLoc(y);  /* must come after alccset() */
  294.          for (i = 0; i < CsetSize; i++)
  295.             cp->bits[i] = cpx->bits[i] | cpy->bits[i];
  296.          return cset(cp);
  297.          }
  298.       }
  299. end
  300.