home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 334.lha / DkbAnim / showprioq.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-01-10  |  3.8 KB  |  170 lines
  1. #include <stdio.h>
  2. #include <exec/types.h>
  3. #include "showprioq.h"
  4.  
  5. char *malloc();
  6.  
  7. struct prioq_struct *pq_new (index_size, value_size)
  8.   int index_size, value_size;
  9.   {
  10.   struct prioq_struct *pq;
  11.   unsigned char *tmp_array;
  12.   int i;
  13.  
  14.   if (index_size > 256)
  15.     return (NULL);
  16.  
  17.   if ((pq = (struct prioq_struct *) malloc
  18.         (sizeof (struct prioq_struct))) == NULL)
  19.     return (NULL);
  20.  
  21.   if ((pq -> queue = (struct q_entry *)
  22.                   malloc (index_size * sizeof (struct q_entry))) == NULL)  {
  23.     free (pq);
  24.     return (NULL);
  25.     }
  26.     
  27.   if ((pq -> array = (unsigned char *) malloc (value_size)) == NULL) {
  28.     free (pq -> queue);
  29.     free (pq);
  30.     return (NULL);
  31.     }
  32.  
  33.   for (i=0, tmp_array = pq -> array ; i<value_size ; i++, tmp_array++)
  34.     *tmp_array = 0;
  35.  
  36.   pq -> queue_size = index_size;
  37.   pq -> array_size = value_size;
  38.   pq -> current_entry = 0;
  39.   return (pq);
  40.   }
  41.  
  42. pq_add (q, index, value)
  43.   struct prioq_struct *q;
  44.   unsigned int index, value;
  45.   {
  46.   unsigned int existing_entry;
  47.  
  48.   if (value >= q -> array_size)
  49.     return (0);
  50.  
  51.   if ((existing_entry = pq_find_value(q, value)) != 0) {
  52.     if ((q -> queue[existing_entry].index) < index)
  53.       (q -> queue[existing_entry].index) = index;
  54.     pq_balance (q, existing_entry);
  55.     }
  56.   else {
  57.     q -> current_entry++;
  58.     if (q -> current_entry >= q -> queue_size) {
  59.       q -> current_entry--;
  60.       q -> array [q->queue[q->current_entry].value] = 0;
  61.       }
  62.  
  63.     q -> queue [q -> current_entry].index = index;
  64.     q -> queue [q -> current_entry].value = value;
  65.     q -> array [value] = q -> current_entry;
  66.     pq_balance (q, q -> current_entry);
  67.     }
  68.   }
  69.     
  70. pq_find_value (q, value)
  71.   struct prioq_struct *q;
  72.   unsigned int value;
  73.   {
  74.   if (value < q -> array_size)
  75.     return (q -> array[value]);
  76.   else
  77.     return (0);
  78.   }
  79.  
  80. pq_balance(q, entry_pos1)
  81.   struct prioq_struct *q;
  82.   unsigned int entry_pos1;
  83.   {
  84.   register struct q_entry *entry1, *entry2;
  85.   register unsigned int tmp_index, tmp_value, entry_pos2;
  86.  
  87.   entry1 = &q->queue[entry_pos1];
  88.  
  89.   if ((entry_pos1 * 2 < q->queue_size)
  90.       && (entry_pos1 * 2 <= q -> current_entry))
  91.     {
  92.     if ((entry_pos1*2+1 > q->current_entry) ||
  93.         (q->queue[entry_pos1*2].index > q->queue[entry_pos1*2+1].index))
  94.       entry_pos2 = entry_pos1*2;
  95.     else
  96.       entry_pos2 = entry_pos1*2+1;
  97.  
  98.     entry2 = &q->queue[entry_pos2];
  99.  
  100.     if (entry1->index < entry2->index) {
  101.       q -> array [entry1->value] = entry_pos2;
  102.       q -> array [entry2->value] = entry_pos1;
  103.  
  104.       tmp_index = entry1->index;
  105.       entry1->index = entry2->index;
  106.       entry2->index = tmp_index;
  107.  
  108.       tmp_value = entry1->value;
  109.       entry1->value = entry2->value;
  110.       entry2->value = tmp_value;
  111.  
  112.       pq_balance (q, entry_pos2);
  113.       }
  114.     }
  115.  
  116.   if (entry_pos1 / 2 >= 1 )
  117.     {
  118.     entry_pos2 = entry_pos1 / 2;
  119.     entry2 = &q->queue[entry_pos2];
  120.     if (entry1->index > entry2->index) {
  121.       q -> array [entry1->value] = entry_pos2;
  122.       q -> array [entry2->value] = entry_pos1;
  123.  
  124.       tmp_index = entry1->index;
  125.       entry1->index = entry2->index;
  126.       entry2->index = tmp_index;
  127.  
  128.       tmp_value = entry1->value;
  129.       entry1->value = entry2->value;
  130.       entry2->value = tmp_value;
  131.  
  132.       pq_balance (q, entry_pos2);
  133.       }
  134.     }
  135.   }
  136.  
  137. pq_get_highest_index(q)
  138.   struct prioq_struct *q;
  139.   {
  140.   if (q -> current_entry >= 1)
  141.     return (q -> queue[1].index);
  142.   else
  143.     return (0);
  144.   }
  145.  
  146. pq_get_highest_value(q)
  147.   struct prioq_struct *q;
  148.   {
  149.   if (q -> current_entry >= 1)
  150.     return (q -> queue[1].value);
  151.   else
  152.     return (0);
  153.   }
  154.  
  155. pq_delete_highest (q)
  156.   struct prioq_struct *q;
  157.   {
  158.   q -> queue[1].index = q -> queue[q -> current_entry].index;
  159.   q -> queue[1].value = q -> queue[q -> current_entry--].value;
  160.   pq_balance (q, 1);
  161.   }
  162.  
  163. pq_free (q)
  164.   struct prioq_struct *q;
  165.   {
  166.   free (q ->queue);
  167.   free (q -> array);
  168.   free (q);
  169.   }
  170.