home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume18 / geneal / part02 / lists.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-08  |  5.1 KB  |  269 lines
  1. /* lists.c - list manipulation routines for geneal
  2.  *
  3.  * 18.Aug.87  jimmc  Initial definition
  4.  * 28.Sep.87  jimmc  Add LAndNot function
  5.  * 17.Oct.87  jimmc  Convert to spin interface
  6.  *  6.Nov.87  jimmc  Name change: xalloc to xallocm, xrealloc to xreallom
  7.  *  4.Jan.88  jimmc  Add LRange
  8.  *  8.Jan.88  jimmc  Add olisttoiarr; lint cleanup
  9.  */
  10.  
  11. #include <stdio.h>
  12. #include "xalloc.h"
  13. #include "geneal.h"
  14. #include "spin.h"
  15.  
  16. extern SPtoken *SPiarrtolist();
  17.  
  18. GroupAppend(group,item)
  19. Group *group;
  20. int item;
  21. {
  22. static char *mm="GroupAppend";
  23.  
  24.     if (group->count >= group->alloc) {
  25.         if (group->alloc==0) group->alloc=15;
  26.         else group->alloc *= 2;
  27.         if (group->n) group->n = (int *)xreallocm((char *)group->n,
  28.                 group->alloc*sizeof(group->n[0]),mm);
  29.         else group->n = (int *)xallocm(
  30.                 group->alloc*sizeof(group->n[0]),mm);
  31.     }
  32.     group->n[group->count++] = item;
  33. }
  34.  
  35. /* Assumes the list is sorted; inserts the new item in sorted order if
  36.  * it does not already exist */
  37. GroupSortedAdd(group,item)
  38. Group *group;
  39. int item;
  40. {
  41. int i,j;
  42.  
  43.     /* The following linear search could be replaced
  44.      * by something more intelligent, like a binary search. */
  45.     for (i=0; i<group->count; i++) {
  46.         if (group->n[i]==item) return;    /* already there */
  47.         if (group->n[i]>item) break;
  48.     }
  49.     GroupAppend(group,item);    /* make space for it */
  50.     if (i<group->count-1) {
  51.         for (j=group->count-1; j>i; j--)
  52.             group->n[j] = group->n[j-1];
  53.         group->n[i] = item;    /* insert in sorted order */
  54.     }
  55. }
  56.  
  57. static int icmp(a,b) int *a,*b; { return *a - *b; }
  58.  
  59. int
  60. llunion(ac1,av1,ac2,av2,pav3)
  61. int ac1, *av1;
  62. int ac2, *av2;
  63. int **pav3;    /* return value - we malloc an array and return pointer */
  64. {
  65. Group clist;
  66. int i1,i2;
  67. int n1,n2;
  68.  
  69.     qsort((char *)av1,ac1,sizeof(av1[0]),icmp);
  70.     qsort((char *)av2,ac2,sizeof(av2[0]),icmp);
  71.     clist.count = clist.alloc = 0;
  72.     clist.n = 0;
  73.     i1 = i2 = 0;
  74.     while (i1<ac1 && i2<ac2) {
  75.         n1 = av1[i1];
  76.         n2 = av2[i2];
  77.         if (n1<n2) {
  78.             if (clist.count==0 || n1>clist.n[clist.count-1]) {
  79.                 GroupAppend(&clist,n1);
  80.             }
  81.             i1++;
  82.         }
  83.         else {    /* n1>=n2 */
  84.             if (clist.count==0 || n2>clist.n[clist.count-1]) {
  85.                 GroupAppend(&clist,n2);
  86.             }
  87.             i2++;
  88.             if (n1==n2) i1++;
  89.         }
  90.     }
  91.     while (i1<ac1) {
  92.         n1 = av1[i1];
  93.         if (clist.count==0 || n1>clist.n[clist.count-1]) {
  94.             GroupAppend(&clist,n1);
  95.         }
  96.         i1++;
  97.     }
  98.     while (i2<ac2) {
  99.         n2 = av2[i2];
  100.         if (clist.count==0 || n2>clist.n[clist.count-1]) {
  101.             GroupAppend(&clist,n2);
  102.         }
  103.         i2++;
  104.     }
  105.     *pav3 = clist.n;
  106.     return clist.count;
  107. }
  108.  
  109. static int
  110. llintersect(ac1,av1,ac2,av2,pav3)
  111. int ac1, *av1;
  112. int ac2, *av2;
  113. int **pav3;    /* return value - we malloc an array and return pointer */
  114. {
  115. Group clist;
  116. int i1,i2;
  117. int n1,n2;
  118.  
  119.     qsort((char *)av1,ac1,sizeof(av1[0]),icmp);
  120.     qsort((char *)av2,ac2,sizeof(av2[0]),icmp);
  121.     clist.count = clist.alloc = 0;
  122.     clist.n = 0;
  123.     i1 = i2 = 0;
  124.     while (i1<ac1 && i2<ac2) {
  125.         n1 = av1[i1];
  126.         n2 = av2[i2];
  127.         if (n1<n2) i1++;
  128.         else if (n1>n2) i2++;
  129.         else {    /* n1==n2 */
  130.             if (clist.count==0 || n2>clist.n[clist.count-1]) {
  131.                 GroupAppend(&clist,n2);
  132.             }
  133.             i1++; i2++;
  134.         }
  135.     }
  136.     *pav3 = clist.n;
  137.     return clist.count;
  138. }
  139.  
  140. static int
  141. llandnot(ac1,av1,ac2,av2,pav3)
  142. int ac1, *av1;
  143. int ac2, *av2;
  144. int **pav3;    /* return value - we malloc an array and return pointer */
  145. {
  146. Group clist;
  147. int i1,i2;
  148. int n1,n2;
  149.  
  150.     qsort((char *)av1,ac1,sizeof(av1[0]),icmp);
  151.     qsort((char *)av2,ac2,sizeof(av2[0]),icmp);
  152.     clist.count = clist.alloc = 0;
  153.     clist.n = 0;
  154.     i2 = 0;
  155.     for (i1=0; i1<ac1; i1++) {
  156.         n1 = av1[i1];
  157.         for ( ; i2<ac2; i2++) {
  158.             n2 = av2[i2];
  159.             if (n1==n2) goto no_insert;
  160.             if (n2>n1) break;
  161.         }
  162.         if (clist.count==0 || n1>clist.n[clist.count-1]) {
  163.             GroupAppend(&clist,n1);
  164.         }
  165. no_insert: ;
  166.     }
  167.     *pav3 = clist.n;
  168.     return clist.count;
  169. }
  170.  
  171. static int
  172. llrange(from,to,pav3)
  173. int from, to;        /* range, inclusive */
  174. int **pav3;    /* return value - we malloc an array and return pointer */
  175. {
  176. int r,i;
  177. int *v;
  178.  
  179.     r = to - from + 1;    /* number of items in the range */
  180.     if (r<=0) return 0;    /* no range */
  181.     v = XALLOC(int,r);
  182.     for (i=0; i<r; i++) {
  183.         v[i] = from+i;
  184.     }
  185.     *pav3 = v;
  186.     return r;
  187. }
  188.  
  189. SPtoken *
  190. Libin2(i1,i2,opfunc)
  191. int i1, i2;
  192. int (*opfunc)();
  193. {
  194. int ac3, *av3;
  195. SPtoken *l;
  196.  
  197.     ac3 = (*opfunc)(i1,i2,&av3);
  198.     l = SPiarrtolist(ac3,av3);
  199.     free((char *)av3);
  200.     return l;
  201. }
  202.  
  203. SPtoken *
  204. LRange(i1,i2)
  205. int i1,i2;
  206. {
  207.     return Libin2(i1,i2,llrange);
  208. }
  209.  
  210. SPtoken *
  211. Lbinop(l1,l2,opfunc)
  212. SPtoken *l1, *l2;
  213. int (*opfunc)();
  214. {
  215. int ac1, *av1;
  216. int ac2, *av2;
  217. int ac3, *av3;
  218. SPtoken *l;
  219.  
  220.     ac1 = olisttoiarr(l1,&av1);
  221.     ac2 = olisttoiarr(l2,&av2);
  222.     ac3 = (*opfunc)(ac1,av1,ac2,av2,&av3);
  223.     l = SPiarrtolist(ac3,av3);
  224.     free((char *)av3);
  225.     return l;
  226. }
  227.  
  228. SPtoken *
  229. LIntersect(l1,l2)
  230. SPtoken *l1, *l2;
  231. {
  232.     return Lbinop(l1,l2,llintersect);
  233. }
  234.  
  235. SPtoken *
  236. LUnion(l1,l2)
  237. SPtoken *l1, *l2;
  238. {
  239.     return Lbinop(l1,l2,llunion);
  240. }
  241.  
  242. SPtoken *
  243. LAndNot(l1,l2)
  244. SPtoken *l1, *l2;
  245. {
  246.     return Lbinop(l1,l2,llandnot);
  247. }
  248.  
  249. int            /* returns number of entries in list */
  250. olisttoiarr(l,pav)
  251. SPtoken *l;        /* list of ints or single int */
  252. int **pav;        /* where to put the return pointer to array of ints */
  253. {
  254. int ac;
  255. int *av;
  256.  
  257.     if (l->type==SPTokInt) {    /* special case for single int */
  258.         ac = 1;
  259.         av = XALLOC(int,1);
  260.         av[0] = l->value.n;
  261.         *pav = av;
  262.     }
  263.     else {
  264.         ac = SPlisttoiarr(l,pav);
  265.     }
  266.     return ac;
  267. }
  268. /* end */
  269.