home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / adaptor.zip / adapt.zip / adaptor / src / permutat.c < prev    next >
Text File  |  1994-01-03  |  11KB  |  385 lines
  1. /*********************************************************************
  2. *                                                                    *
  3. *  Author      : Dr. Thomas Brandes, GMD, I1.HR                      *
  4. *  Date        : Mar 93                                              *
  5. *  Last Update : Mar 93                                              *
  6. *                                                                    *
  7. *  Module      : permutations.c                                      *
  8. *                                                                    *
  9. *********************************************************************/
  10.  
  11. # include "permutat.h"
  12.  
  13.        /*************************************************
  14.        *                                                *
  15.        *  some operations on Permutations               *
  16.        *                                                *
  17.        *  make_id_permuatation (5)  :  1 2 3 4 5        *
  18.        *                                                *
  19.        *************************************************/
  20.  
  21. Permutation make_id_permutation (n)          /* create identity */
  22. int n;
  23.  
  24. { Permutation perm;
  25.   int i;
  26.  
  27.   if (n > MAX_DIMENSIONS)
  28.     { printf ("AdaptDistriubtions: make_id_permutation, %d too big\n", n);
  29.       exit (-1);
  30.     }
  31.  
  32.   perm.n = n;
  33.   for (i=1; i<=n; i++) perm.pa[i-1] = i;
  34.  
  35.   return (perm);
  36.  
  37. } /* make_id_permutation */
  38.  
  39. bool is_id_permutation (perm)
  40.  
  41. Permutation perm;
  42.  
  43. { bool ok;
  44.  
  45.   int i;
  46.  
  47.   ok = true;
  48.  
  49.   for (i=1; i<=perm.n; i++)
  50.     ok = ok && perm.pa[i-1] == i;
  51.  
  52.   return (ok);
  53.  
  54. } /* is_id_permutation */
  55.  
  56. int new_perm_position (perm, pos)
  57. Permutation perm;
  58. int pos;
  59. { int i, newpos;
  60.  
  61.   newpos = 0;
  62.   for (i=1; i<=perm.n; i++)
  63.      if (perm.pa[i-1] == pos)
  64.         newpos = i;
  65.  
  66.   if (newpos == 0)
  67.       { printf ("internal error for new_perm_position\n");
  68.         exit(-1);
  69.       }
  70.   return (newpos);
  71. }
  72.  
  73.        /****************************************************
  74.        *                                                   *
  75.        *       1  2  3  4  5                               *
  76.        *  p :  3  4  5  2  1                               *
  77.        *                                                   *
  78.        *   olddim = 4     newdim = 2                       *
  79.        *                                                   *
  80.        *  n :  3  4  2  1                                  *
  81.        *                                                   *
  82.        ****************************************************/
  83.  
  84. Permutation reduce_permutation (p, olddim, newdim)
  85. Permutation p;
  86. int olddim, newdim;
  87.  
  88. { Permutation new_perm;
  89.   int i;
  90.  
  91.   new_perm = p;
  92.   /* decrease all entries greater than olddim by  */
  93.   for (i=0; i<new_perm.n; i++)
  94.      if (new_perm.pa[i] > olddim)
  95.         new_perm.pa[i] = new_perm.pa[i]-1;
  96.   /* remove entry for newdim, this should be olddim */
  97.   if (new_perm.pa[newdim-1] != olddim)
  98.       { printf ("internal error for reduce_permutation\n");
  99.         exit (-1);
  100.       }
  101.   for (i=newdim; i<new_perm.n; i++)
  102.      new_perm.pa[i-1] = new_perm.pa[i];
  103.   new_perm.n = new_perm.n-1;
  104.  
  105.   return (new_perm);
  106. }
  107.  
  108. bool equal_permutations (perm1, perm2)
  109.  
  110. Permutation perm1, perm2;
  111.  
  112. { bool ok;
  113.   int i;
  114.  
  115.   ok = (perm1.n == perm2.n);
  116.   if (ok)
  117.     { for (i=0; i<perm1.n; i++)
  118.         ok = ok && (perm1.pa[i] == perm2.pa[i]);
  119.     }
  120.   return (ok);
  121. }
  122.  
  123. bool conform_permutations (perm1, perm2)
  124.  
  125. Permutation perm1, perm2;
  126.  
  127. {  bool ok;
  128.  
  129.    if (perm1.n == 0)
  130.       ok = true;
  131.     else if (perm2.n == 0)
  132.       ok = true;
  133.     else
  134.       ok = equal_permutations (perm1, perm2);
  135.  
  136.    return (ok);
  137.  
  138. } /* conform_permutations */
  139.  
  140.        /****************************************************
  141.        *                                                   *
  142.        *  transpose_permutations (perm1, perm2)            *
  143.        *                                                   *
  144.        *   true  iff last dimensions are switched          *
  145.        *                                                   *
  146.        ****************************************************/
  147.  
  148. bool transpose_permutations (perm1, perm2)
  149. Permutation perm1, perm2;
  150. {  bool ok;
  151.    int i, n;
  152.    n = perm1.n;
  153.    if (n != perm2.n) return (false);
  154.    if (n < 2) return (false);
  155.    ok = true;
  156.    for (i=0; i<n-2; i++)
  157.      ok = ok && (perm1.pa[i] == perm2.pa[i]);
  158.    ok = ok && (perm1.pa[n-2] == perm2.pa[n-1]);
  159.    ok = ok && (perm1.pa[n-1] == perm2.pa[n-2]);
  160.    return (ok);
  161. }
  162.  
  163. Permutation merge_permutation (perm1, perm2)
  164.  
  165. Permutation perm1, perm2;
  166.  
  167. { if (perm1.n == 0)
  168.      return (perm2);
  169.    else
  170.      return (perm1);
  171.  
  172. } /* merge_permutation */
  173.  
  174. void print_permutation (perm)
  175. Permutation perm;
  176. { int i;
  177.   printf ("Permutation (n=%d) : ", perm.n);
  178.   for (i=1; i<=perm.n; i++) printf ("%d ", perm.pa[i-1]);
  179.   printf ("\n");
  180. }
  181.  
  182.        /****************************************************
  183.        *                                                   *
  184.        *  make permutation from the current distribution   *
  185.        *                                                   *
  186.        *  A (N1,N2,N3,N4,N5)  (*,BLOCK,*,BLOCK,*)          *
  187.        *                                                   *
  188.        *  ->      1, 3, 5, 2, 4                            *
  189.        *                                                   *
  190.        ****************************************************/
  191.  
  192. Permutation implied_distribution_permutation (dist)
  193.  
  194. DistributedDimensions dist;
  195.  
  196. { Permutation s_perm, d_perm;
  197.   int k, n;
  198.   int serial_n, dist_n;
  199.  
  200.   n        = dist.no_dims;
  201.   serial_n = 0;
  202.   dist_n   = 0;
  203.  
  204.   for (k=1; k<=n; k++)
  205.     { if (dist.DimsArray[k-1] > 0)    /* distributed */
  206.         { /* distributed */
  207.           d_perm.pa[dist_n] = k;
  208.           dist_n += 1;
  209.         }
  210.       else
  211.         { /* serial dimension */
  212.           s_perm.pa[serial_n] = k;
  213.           serial_n += 1;
  214.         }
  215.     }
  216.  
  217.   /* serial dimensions are the first ones, append parallel dims */
  218.  
  219.   for (k=0; k<dist_n; k++)
  220.     s_perm.pa[serial_n+k] = d_perm.pa[k];
  221.  
  222.   s_perm.n = n;
  223.  
  224.   return (s_perm);
  225.  
  226. } /* implied_distribution_permutation */
  227.  
  228.        /****************************************************
  229.        *                                                   *
  230.        *  index_list returns a sequence of ranks of index  *
  231.        *                                                   *
  232.        *  [1:n,A,I,J,B] ->  1  2  0  0  3                  *
  233.        *                                                   *
  234.        ****************************************************/
  235.  
  236. Permutation index_list (indexes)
  237.  
  238. tTree indexes;
  239.  
  240. { Permutation perm;
  241.   int i, n, count;
  242.   tTree hl, elem;
  243.  
  244.   n      = TreeListLength (indexes);
  245.   perm.n = n;
  246.   count  = 0;
  247.   hl     = indexes;
  248.  
  249.   for (i=0; i<n; i++)
  250.      { elem = hl->BTE_LIST.Elem;
  251.        hl   = hl->BTE_LIST.Next;
  252.        if (TreeRank (elem) > 0)
  253.          { count ++;
  254.            perm.pa[i] = count;
  255.          }
  256.         else
  257.          perm.pa[i] = 0;
  258.      }
  259.  
  260.   return (perm);
  261.  
  262. }  /* index_list */
  263.  
  264.        /****************************************************
  265.        *                                                   *
  266.        *  get_rank_permutation :                           *
  267.        *                                                   *
  268.        *  index_vector  :   1  0  2  0  3                  *
  269.        *  perm          :   4  1  5  2  3                  *
  270.        *                                                   *
  271.        *  results in    :   0  1  3  0  2                  *
  272.        *                                                   *
  273.        *  compressed    :   1  3  2  0  0                  *
  274.        *                                                   *
  275.        ****************************************************/
  276.  
  277. Permutation get_rank_permutation (index_vector, perm)
  278.  
  279. Permutation index_vector, perm;
  280.  
  281. { Permutation new;
  282.   int i, count;
  283.  
  284.   /* permute index_vector to new */
  285.  
  286.   new.n = index_vector.n;
  287.   for (i=0; i<new.n; i++)
  288.     new.pa[i] = index_vector.pa [perm.pa[i] - 1];
  289.  
  290.   /* compress the new index vector  */
  291.  
  292.   count = 0;
  293.   for (i=0; i<new.n; i++)
  294.     if (new.pa[i] > 0)
  295.       { new.pa[count] = new.pa[i];
  296.         count ++;
  297.       }
  298.   new.n = count;
  299.  
  300.   return (new);
  301.  
  302. } /* get_rank_permutation */
  303.  
  304.        /****************************************************
  305.        *                                                   *
  306.        *  switch_index_types :                             *
  307.        *  switch_indexes     :                             *
  308.        *                                                   *
  309.        *     perm = 4  2  3  1  5                          *
  310.        *                                                   *
  311.        *  (N1,N2,N3,N4,N5)  -> (N4,N2,N3,N1,N5)            *
  312.        *                                                   *
  313.        ****************************************************/
  314.  
  315. void switch_index_types (typelist, perm)
  316. tTree typelist;
  317. Permutation perm;
  318.  
  319. { tTree tarray [MAX_DIMENSIONS];
  320.   tTree hlist;
  321.   int i;
  322.  
  323.   hlist = typelist;
  324.   for (i=0; i<perm.n; i++)
  325.    { tarray[i] = hlist->TYPE_LIST.Elem;
  326.      hlist     = hlist->TYPE_LIST.Next;
  327.    }
  328.  
  329.   hlist = typelist;
  330.   for (i=0; i<perm.n; i++)
  331.    { hlist->TYPE_LIST.Elem = tarray[perm.pa[i]-1];
  332.      hlist     = hlist->TYPE_LIST.Next;
  333.    }
  334.  
  335. } /* switch_index_types */
  336.  
  337. void switch_indexes (indexlist, perm)
  338. tTree indexlist;
  339. Permutation perm;
  340.  
  341. { tTree tarray [MAX_DIMENSIONS];
  342.   tTree hlist;
  343.   int i;
  344.  
  345.   /* put indexes in an array */
  346.   hlist = indexlist;
  347.   for (i=0; i<perm.n; i++)
  348.    { tarray[i] = hlist->BTE_LIST.Elem;
  349.      hlist     = hlist->BTE_LIST.Next;
  350.    }
  351.  
  352.   /* refill with permuted list */
  353.   hlist = indexlist;
  354.   for (i=0; i<perm.n; i++)
  355.    { hlist->BTE_LIST.Elem = tarray[perm.pa[i]-1];
  356.      hlist     = hlist->BTE_LIST.Next;
  357.    }
  358.  
  359. } /* switch_indexes */
  360.  
  361. void switch_parameters (paramlist, perm)
  362. tTree paramlist;
  363. Permutation perm;
  364.  
  365. { tTree tarray [MAX_DIMENSIONS];
  366.   tTree hlist;
  367.   int i;
  368.  
  369.   /* put parameters in an array */
  370.   hlist = paramlist;
  371.   for (i=0; i<perm.n; i++)
  372.    { tarray[i] = hlist->BTP_LIST.Elem;
  373.      hlist     = hlist->BTP_LIST.Next;
  374.    }
  375.  
  376.   /* refill with permuted list */
  377.   hlist = paramlist;
  378.   for (i=0; i<perm.n; i++)
  379.    { hlist->BTP_LIST.Elem = tarray[perm.pa[i]-1];
  380.      hlist     = hlist->BTP_LIST.Next;
  381.    }
  382.  
  383. } /* switch_parameters */
  384.  
  385.