home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsv / ch7_5 / misc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-04  |  2.3 KB  |  140 lines
  1. #include "basic.h"
  2. #include <sys/time.h>
  3. #include <math.h>
  4.  
  5. #ifdef __STDC__
  6. extern double log2(double);
  7. #else
  8. extern double log2();
  9. #endif
  10.  
  11. static int choose_idx;
  12. static int permute[SEGSIZE];
  13.  
  14. /* Generate a random permutation of the segments 1..n */
  15. int generate_random_ordering(n)
  16.      int n;
  17. {
  18.   struct timeval tval;
  19.   struct timezone tzone;
  20.   register int i;
  21.   int m, st[SEGSIZE], *p;
  22.   
  23.   choose_idx = 1;
  24.   gettimeofday(&tval, &tzone);
  25.   srand48(tval.tv_sec);
  26.  
  27.   for (i = 0; i <= n; i++)
  28.     st[i] = i;
  29.  
  30.   p = st;
  31.   for (i = 1; i <= n; i++, p++)
  32.     {
  33.       m = lrand48() % (n + 1 - i) + 1;
  34.       permute[i] = p[m];
  35.       if (m != 1)
  36.     p[m] = p[1];
  37.     }
  38.   return 0;
  39. }
  40.  
  41.   
  42. /* Return the next segment in the generated random ordering of all the */
  43. /* segments in S */
  44. int choose_segment()
  45. {
  46.   int i;
  47. /*  
  48. #ifdef DEBUG
  49.   fprintf(stderr, "choose_segment: %d\n", permute[choose_idx]);
  50. #endif 
  51.   return permute[choose_idx++];
  52. */
  53.  
  54. #ifdef CHOOSE_MANUAL
  55.   printf("Enter seg: ");
  56.   scanf("%d", &i);
  57.   return i;
  58. #else
  59.   
  60. #ifdef DEBUG
  61.   fprintf(stderr, "choose_segment: %d\n", permute[choose_idx]);
  62. #endif 
  63.   return permute[choose_idx++];
  64. #endif
  65. }
  66.  
  67.  
  68. int inserted(segnum, whichpt)
  69.      int segnum;
  70.      int whichpt;
  71. {
  72.   int n1, n2;
  73.  
  74.   n1 = segnum % global.nseg + 1; /* next seg. */
  75.   n2 = (segnum - 1 + global.nseg - 1) % global.nseg + 1; /* prev. */ 
  76.  
  77.   if (whichpt == FIRSTPT)
  78.     return seg[n2].is_inserted;
  79.   else
  80.     return seg[n1].is_inserted;
  81. }
  82.  
  83.  
  84. #ifdef STANDALONE
  85.  
  86. /* Read in the list of vertices from infile */
  87. int read_segments(infile)
  88.      FILE *infile;
  89. {
  90.   int nseg;
  91.   register int i;
  92.  
  93.   memset((void *)seg, 0, sizeof(seg));
  94.   i = 1; 
  95.   nseg = 0;
  96.   while (fscanf(infile, "%lf%lf", &seg[i].v0.x, &seg[i].v0.y) == 2)
  97.     {
  98.       seg[i - 1].v1.x = seg[i].v0.x;
  99.       seg[i - 1].v1.y = seg[i].v0.y;
  100.       seg[i].is_inserted = FALSE;
  101.       i++;
  102.       nseg++;
  103.     }
  104.   seg[nseg].v1.x = seg[1].v0.x;
  105.   seg[nseg].v1.y = seg[1].v0.y;
  106.   
  107.   global.nseg = nseg;
  108.   return nseg;
  109. }
  110.  
  111. #endif
  112.  
  113.  
  114. /* Get log*n for given n */
  115. int math_logstar_n(n)
  116.      int n;
  117. {
  118.   register int i;
  119.   double v;
  120.   
  121.   for (i = 0, v = (double) n; v >= 1; i++)
  122.     v = log2(v);
  123.   
  124.   return (i - 1);
  125. }
  126.   
  127.  
  128. int math_N(n, h)
  129.      int n;
  130.      int h;
  131. {
  132.   register int i;
  133.   double v;
  134.  
  135.   for (i = 0, v = (int) n; i < h; i++)
  136.     v = log2(v);
  137.   
  138.   return (int) ceil((double) 1.0*n/v);
  139. }
  140.