home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / mesch12a.zip / ivecop.c < prev    next >
C/C++ Source or Header  |  1994-01-13  |  10KB  |  435 lines
  1.  
  2. /**************************************************************************
  3. **
  4. ** Copyright (C) 1993 David E. Steward & Zbigniew Leyk, all rights reserved.
  5. **
  6. **                 Meschach Library
  7. ** 
  8. ** This Meschach Library is provided "as is" without any express 
  9. ** or implied warranty of any kind with respect to this software. 
  10. ** In particular the authors shall not be liable for any direct, 
  11. ** indirect, special, incidental or consequential damages arising 
  12. ** in any way from use of the software.
  13. ** 
  14. ** Everyone is granted permission to copy, modify and redistribute this
  15. ** Meschach Library, provided:
  16. **  1.  All copies contain this copyright notice.
  17. **  2.  All modified copies shall carry a notice stating who
  18. **      made the last modification and the date of such modification.
  19. **  3.  No charge is made for this software or works derived from it.  
  20. **      This clause shall not be construed as constraining other software
  21. **      distributed on the same medium as this software, nor is a
  22. **      distribution fee considered a charge.
  23. **
  24. ***************************************************************************/
  25.  
  26.  
  27. /* ivecop.c  */
  28.  
  29. #include    <stdio.h>
  30. #include     "matrix.h"
  31.  
  32. static    char    rcsid[] = "$Id: ivecop.c,v 1.5 1994/01/13 05:45:30 des Exp $";
  33.  
  34. static char    line[MAXLINE];
  35.  
  36.  
  37.  
  38. /* iv_get -- get integer vector -- see also memory.c */
  39. IVEC    *iv_get(dim)
  40. int    dim;
  41. {
  42.    IVEC    *iv;
  43.    /* u_int    i; */
  44.    
  45.    if (dim < 0)
  46.      error(E_NEG,"iv_get");
  47.  
  48.    if ((iv=NEW(IVEC)) == IVNULL )
  49.      error(E_MEM,"iv_get");
  50.    else if (mem_info_is_on()) {
  51.       mem_bytes(TYPE_IVEC,0,sizeof(IVEC));
  52.       mem_numvar(TYPE_IVEC,1);
  53.    }
  54.    
  55.    iv->dim = iv->max_dim = dim;
  56.    if ((iv->ive = NEW_A(dim,int)) == (int *)NULL )
  57.      error(E_MEM,"iv_get");
  58.    else if (mem_info_is_on()) {
  59.       mem_bytes(TYPE_IVEC,0,dim*sizeof(int));
  60.    }
  61.    
  62.    return (iv);
  63. }
  64.  
  65. /* iv_free -- returns iv & asoociated memory back to memory heap */
  66. int    iv_free(iv)
  67. IVEC    *iv;
  68. {
  69.    if ( iv==IVNULL || iv->dim > MAXDIM )
  70.      /* don't trust it */
  71.      return (-1);
  72.    
  73.    if ( iv->ive == (int *)NULL ) {
  74.       if (mem_info_is_on()) {
  75.      mem_bytes(TYPE_IVEC,sizeof(IVEC),0);
  76.      mem_numvar(TYPE_IVEC,-1);
  77.       }
  78.       free((char *)iv);
  79.    }
  80.    else
  81.    {
  82.       if (mem_info_is_on()) {
  83.      mem_bytes(TYPE_IVEC,sizeof(IVEC)+iv->max_dim*sizeof(int),0);
  84.      mem_numvar(TYPE_IVEC,-1);
  85.       }    
  86.       free((char *)iv->ive);
  87.       free((char *)iv);
  88.    }
  89.    
  90.    return (0);
  91. }
  92.  
  93. /* iv_resize -- returns the IVEC with dimension new_dim
  94.    -- iv is set to the zero vector */
  95. IVEC    *iv_resize(iv,new_dim)
  96. IVEC    *iv;
  97. int    new_dim;
  98. {
  99.    int    i;
  100.    
  101.    if (new_dim < 0)
  102.      error(E_NEG,"iv_resize");
  103.  
  104.    if ( ! iv )
  105.      return iv_get(new_dim);
  106.    
  107.    if (new_dim == iv->dim)
  108.      return iv;
  109.  
  110.    if ( new_dim > iv->max_dim )
  111.    {
  112.       if (mem_info_is_on()) {
  113.      mem_bytes(TYPE_IVEC,iv->max_dim*sizeof(int),
  114.               new_dim*sizeof(int));
  115.       }
  116.       iv->ive = RENEW(iv->ive,new_dim,int);
  117.       if ( ! iv->ive )
  118.     error(E_MEM,"iv_resize");
  119.       iv->max_dim = new_dim;
  120.    }
  121.    if ( iv->dim <= new_dim )
  122.      for ( i = iv->dim; i < new_dim; i++ )
  123.        iv->ive[i] = 0;
  124.    iv->dim = new_dim;
  125.    
  126.    return iv;
  127. }
  128.  
  129. /* iv_copy -- copy integer vector in to out
  130.    -- out created/resized if necessary */
  131. IVEC    *iv_copy(in,out)
  132. IVEC    *in, *out;
  133. {
  134.    int        i;
  135.    
  136.    if ( ! in )
  137.      error(E_NULL,"iv_copy");
  138.    out = iv_resize(out,in->dim);
  139.    for ( i = 0; i < in->dim; i++ )
  140.      out->ive[i] = in->ive[i];
  141.    
  142.    return out;
  143. }
  144.  
  145. /* iv_move -- move selected pieces of an IVEC
  146.     -- moves the length dim0 subvector with initial index i0
  147.        to the corresponding subvector of out with initial index i1
  148.     -- out is resized if necessary */
  149. IVEC    *iv_move(in,i0,dim0,out,i1)
  150. IVEC    *in, *out;
  151. int    i0, dim0, i1;
  152. {
  153.     if ( ! in )
  154.     error(E_NULL,"iv_move");
  155.     if ( i0 < 0 || dim0 < 0 || i1 < 0 ||
  156.      i0+dim0 > in->dim )
  157.     error(E_BOUNDS,"iv_move");
  158.  
  159.     if ( (! out) || i1+dim0 > out->dim )
  160.     out = iv_resize(out,i1+dim0);
  161.  
  162.     MEM_COPY(&(in->ive[i0]),&(out->ive[i1]),dim0*sizeof(int));
  163.  
  164.     return out;
  165. }
  166.  
  167. /* iv_add -- integer vector addition -- may be in-situ */
  168. IVEC    *iv_add(iv1,iv2,out)
  169. IVEC    *iv1,*iv2,*out;
  170. {
  171.    u_int    i;
  172.    int    *out_ive, *iv1_ive, *iv2_ive;
  173.    
  174.    if ( iv1==IVNULL || iv2==IVNULL )
  175.      error(E_NULL,"iv_add");
  176.    if ( iv1->dim != iv2->dim )
  177.      error(E_SIZES,"iv_add");
  178.    if ( out==IVNULL || out->dim != iv1->dim )
  179.      out = iv_resize(out,iv1->dim);
  180.    
  181.    out_ive = out->ive;
  182.    iv1_ive = iv1->ive;
  183.    iv2_ive = iv2->ive;
  184.    
  185.    for ( i = 0; i < iv1->dim; i++ )
  186.      out_ive[i] = iv1_ive[i] + iv2_ive[i];
  187.    
  188.    return (out);
  189. }
  190.  
  191.  
  192.  
  193. /* iv_sub -- integer vector addition -- may be in-situ */
  194. IVEC    *iv_sub(iv1,iv2,out)
  195. IVEC    *iv1,*iv2,*out;
  196. {
  197.    u_int    i;
  198.    int    *out_ive, *iv1_ive, *iv2_ive;
  199.    
  200.    if ( iv1==IVNULL || iv2==IVNULL )
  201.      error(E_NULL,"iv_sub");
  202.    if ( iv1->dim != iv2->dim )
  203.      error(E_SIZES,"iv_sub");
  204.    if ( out==IVNULL || out->dim != iv1->dim )
  205.      out = iv_resize(out,iv1->dim);
  206.    
  207.    out_ive = out->ive;
  208.    iv1_ive = iv1->ive;
  209.    iv2_ive = iv2->ive;
  210.    
  211.    for ( i = 0; i < iv1->dim; i++ )
  212.      out_ive[i] = iv1_ive[i] - iv2_ive[i];
  213.    
  214.    return (out);
  215. }
  216.  
  217. /* iv_foutput -- print a representation of iv on stream fp */
  218. void    iv_foutput(fp,iv)
  219. FILE    *fp;
  220. IVEC    *iv;
  221. {
  222.    int    i;
  223.    
  224.    fprintf(fp,"IntVector: ");
  225.    if ( iv == IVNULL )
  226.    {
  227.       fprintf(fp,"**** NULL ****\n");
  228.       return;
  229.    }
  230.    fprintf(fp,"dim: %d\n",iv->dim);
  231.    for ( i = 0; i < iv->dim; i++ )
  232.    {
  233.       if ( (i+1) % 8 )
  234.     fprintf(fp,"%8d ",iv->ive[i]);
  235.       else
  236.     fprintf(fp,"%8d\n",iv->ive[i]);
  237.    }
  238.    if ( i % 8 )
  239.      fprintf(fp,"\n");
  240. }
  241.  
  242.  
  243. /* iv_finput -- input integer vector from stream fp */
  244. IVEC    *iv_finput(fp,x)
  245. FILE    *fp;
  246. IVEC    *x;
  247. {
  248.    IVEC    *iiv_finput(),*biv_finput();
  249.    
  250.    if ( isatty(fileno(fp)) )
  251.      return iiv_finput(fp,x);
  252.    else
  253.      return biv_finput(fp,x);
  254. }
  255.  
  256. /* iiv_finput -- interactive input of IVEC iv */
  257. IVEC    *iiv_finput(fp,iv)
  258. FILE    *fp;
  259. IVEC    *iv;
  260. {
  261.    u_int    i,dim,dynamic;    /* dynamic set if memory allocated here */
  262.    
  263.    /* get dimension */
  264.    if ( iv != (IVEC *)NULL && iv->dim<MAXDIM )
  265.    {    dim = iv->dim;    dynamic = FALSE;    }
  266.    else
  267.    {
  268.       dynamic = TRUE;
  269.       do
  270.       {
  271.      fprintf(stderr,"IntVector: dim: ");
  272.      if ( fgets(line,MAXLINE,fp)==NULL )
  273.        error(E_INPUT,"iiv_finput");
  274.       } while ( sscanf(line,"%u",&dim)<1 || dim>MAXDIM );
  275.       iv = iv_get(dim);
  276.    }
  277.    
  278.    /* input elements */
  279.    for ( i=0; i<dim; i++ )
  280.      do
  281.      {
  282.       redo:
  283.     fprintf(stderr,"entry %u: ",i);
  284.     if ( !dynamic )
  285.       fprintf(stderr,"old: %-9d  new: ",iv->ive[i]);
  286.     if ( fgets(line,MAXLINE,fp)==NULL )
  287.       error(E_INPUT,"iiv_finput");
  288.     if ( (*line == 'b' || *line == 'B') && i > 0 )
  289.     {    i--;    dynamic = FALSE;    goto redo;       }
  290.     if ( (*line == 'f' || *line == 'F') && i < dim-1 )
  291.     {    i++;    dynamic = FALSE;    goto redo;       }
  292.      } while ( *line=='\0' || sscanf(line,"%d",&iv->ive[i]) < 1 );
  293.    
  294.    return (iv);
  295. }
  296.  
  297. /* biv_finput -- batch-file input of IVEC iv */
  298. IVEC    *biv_finput(fp,iv)
  299. FILE    *fp;
  300. IVEC    *iv;
  301. {
  302.    u_int    i,dim;
  303.    int    io_code;
  304.    
  305.    /* get dimension */
  306.    skipjunk(fp);
  307.    if ((io_code=fscanf(fp," IntVector: dim:%u",&dim)) < 1 ||
  308.        dim>MAXDIM )
  309.      error(io_code==EOF ? 7 : 6,"biv_finput");
  310.    
  311.    /* allocate memory if necessary */
  312.    if ( iv==(IVEC *)NULL || iv->dim<dim )
  313.      iv = iv_resize(iv,dim);
  314.    
  315.    /* get entries */
  316.    skipjunk(fp);
  317.    for ( i=0; i<dim; i++ )
  318.      if ((io_code=fscanf(fp,"%d",&iv->ive[i])) < 1 )
  319.        error(io_code==EOF ? 7 : 6,"biv_finput");
  320.    
  321.    return (iv);
  322. }
  323.  
  324. /* iv_dump -- dumps all the contents of IVEC iv onto stream fp */
  325. void    iv_dump(fp,iv)
  326. FILE*fp;
  327. IVEC*iv;
  328. {
  329.    int        i;
  330.    
  331.    fprintf(fp,"IntVector: ");
  332.    if ( ! iv )
  333.    {
  334.       fprintf(fp,"**** NULL ****\n");
  335.       return;
  336.    }
  337.    fprintf(fp,"dim: %d, max_dim: %d\n",iv->dim,iv->max_dim);
  338.    fprintf(fp,"ive @ 0x%lx\n",(long)(iv->ive));
  339.    for ( i = 0; i < iv->max_dim; i++ )
  340.    {
  341.       if ( (i+1) % 8 )
  342.     fprintf(fp,"%8d ",iv->ive[i]);
  343.       else
  344.     fprintf(fp,"%8d\n",iv->ive[i]);
  345.    }
  346.    if ( i % 8 )
  347.      fprintf(fp,"\n");
  348. }    
  349.  
  350. #define    MAX_STACK    60
  351.  
  352.  
  353. /* iv_sort -- sorts vector x, and generates permutation that gives the order
  354.    of the components; x = [1.3, 3.7, 0.5] -> [0.5, 1.3, 3.7] and
  355.    the permutation is order = [2, 0, 1].
  356.    -- if order is NULL on entry then it is ignored
  357.    -- the sorted vector x is returned */
  358. IVEC    *iv_sort(x, order)
  359. IVEC    *x;
  360. PERM    *order;
  361. {
  362.    int        *x_ive, tmp, v;
  363.    /* int        *order_pe; */
  364.    int        dim, i, j, l, r, tmp_i;
  365.    int        stack[MAX_STACK], sp;
  366.    
  367.    if ( ! x )
  368.      error(E_NULL,"v_sort");
  369.    if ( order != PNULL && order->size != x->dim )
  370.      order = px_resize(order, x->dim);
  371.    
  372.    x_ive = x->ive;
  373.    dim = x->dim;
  374.    if ( order != PNULL )
  375.      px_ident(order);
  376.    
  377.    if ( dim <= 1 )
  378.      return x;
  379.    
  380.    /* using quicksort algorithm in Sedgewick,
  381.       "Algorithms in C", Ch. 9, pp. 118--122 (1990) */
  382.    sp = 0;
  383.    l = 0;    r = dim-1;    v = x_ive[0];
  384.    for ( ; ; )
  385.    {
  386.       while ( r > l )
  387.       {
  388.      /* "i = partition(x_ive,l,r);" */
  389.      v = x_ive[r];
  390.      i = l-1;
  391.      j = r;
  392.      for ( ; ; )
  393.      {
  394.         while ( x_ive[++i] < v )
  395.           ;
  396.         while ( x_ive[--j] > v )
  397.           ;
  398.         if ( i >= j )    break;
  399.         
  400.         tmp = x_ive[i];
  401.         x_ive[i] = x_ive[j];
  402.         x_ive[j] = tmp;
  403.         if ( order != PNULL )
  404.         {
  405.            tmp_i = order->pe[i];
  406.            order->pe[i] = order->pe[j];
  407.            order->pe[j] = tmp_i;
  408.         }
  409.      }
  410.      tmp = x_ive[i];
  411.      x_ive[i] = x_ive[r];
  412.      x_ive[r] = tmp;
  413.      if ( order != PNULL )
  414.      {
  415.         tmp_i = order->pe[i];
  416.         order->pe[i] = order->pe[r];
  417.         order->pe[r] = tmp_i;
  418.      }
  419.      
  420.      if ( i-l > r-i )
  421.      {   stack[sp++] = l;   stack[sp++] = i-1;   l = i+1;   }
  422.      else
  423.      {   stack[sp++] = i+1;   stack[sp++] = r;   r = i-1;   }
  424.       }
  425.       
  426.       /* recursion elimination */
  427.       if ( sp == 0 )
  428.     break;
  429.       r = stack[--sp];
  430.       l = stack[--sp];
  431.    }
  432.    
  433.    return x;
  434. }
  435.