home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / System / Mesa-3.1 / src-glu / tess_heap.c < prev    next >
C/C++ Source or Header  |  1999-12-06  |  7KB  |  314 lines
  1. /* $Id: tess_heap.c,v 1.9.2.4 1999/12/05 02:04:31 gareth Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  3.1
  6.  *
  7.  * Copyright (C) 1999  Brian Paul   All Rights Reserved.
  8.  *
  9.  * Permission is hereby granted, free of charge, to any person obtaining a
  10.  * copy of this software and associated documentation files (the "Software"),
  11.  * to deal in the Software without restriction, including without limitation
  12.  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  13.  * and/or sell copies of the Software, and to permit persons to whom the
  14.  * Software is furnished to do so, subject to the following conditions:
  15.  *
  16.  * The above copyright notice and this permission notice shall be included
  17.  * in all copies or substantial portions of the Software.
  18.  *
  19.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  20.  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  22.  * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  23.  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  24.  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25.  */
  26.  
  27. /*****************************************************************************
  28.  *
  29.  * GLU 1.3 Polygon Tessellation - Implementation of priority queue
  30.  *
  31.  * Gareth Hughes <garethh@bell-labs.com>, April 1999
  32.  *
  33.  *****************************************************************************/
  34.  
  35. #include <stdio.h>
  36. #include <stdlib.h>
  37. #include <math.h>
  38.  
  39. #include "gluP.h"
  40.  
  41. #include "tess.h"
  42. #include "tess_macros.h"
  43. #include "tess_heap.h"
  44.  
  45.  
  46. /*****************************************************************************
  47.  * Internal definitions:
  48.  *****************************************************************************/
  49.  
  50. #define PARENT(i)        (((i+1)>>1)-1)
  51. #define LEFT(i)            (((i+1)<<1)-1)
  52. #define RIGHT(i)        ((i+1)<<1)
  53.  
  54.  
  55.  
  56. /*****************************************************************************
  57.  *
  58.  *                HEAP FUNCTIONS
  59.  *
  60.  *****************************************************************************/
  61.  
  62.  
  63. /*****************************************************************************
  64.  * heapify
  65.  *
  66.  * Heapify the heap :)
  67.  *****************************************************************************/
  68. static void heapify( heap_t *heap, GLint n )
  69. {
  70.     GLint    left = LEFT( n );
  71.     GLint    right = RIGHT( n );
  72.     GLint    largest;
  73.  
  74.     if ( ( left < heap->size ) &&
  75.      ( heap->elements[left]->value > heap->elements[n]->value ) )
  76.     {
  77.     largest = left;
  78.     }
  79.     else
  80.     {
  81.     largest = n;
  82.     }
  83.  
  84.     if ( ( right < heap->size ) &&
  85.      ( heap->elements[right]->value >
  86.        heap->elements[largest]->value ) )
  87.     {
  88.     largest = right;
  89.     }
  90.  
  91.     if ( largest != n )
  92.     {
  93.     heap_elt_t    *element;
  94.  
  95.     element = heap->elements[n];
  96.  
  97.     heap->elements[n] = heap->elements[largest];
  98.     heap->elements[n]->index = n;
  99.  
  100.     heap->elements[largest] = element;
  101.     heap->elements[largest]->index = largest;
  102.  
  103.     heapify( heap, largest );
  104.     }
  105. }
  106.  
  107.  
  108. /*****************************************************************************
  109.  * heap_init
  110.  *
  111.  * Allocate and initialize a new heap.
  112.  *****************************************************************************/
  113. heap_t *heap_init()
  114. {
  115.     heap_t    *heap;
  116.     GLint    i;
  117.  
  118.     heap = (heap_t *) malloc( sizeof(heap_t) );
  119.     if ( heap == NULL ) {
  120.     return NULL;
  121.     }
  122.  
  123.     heap->elements = (heap_elt_t **)
  124.     malloc( HEAP_ALLOC * sizeof(heap_elt_t *) );
  125.     if ( heap->elements == NULL ) {
  126.     free( heap );
  127.     return NULL;
  128.     }
  129.  
  130.     heap->length = HEAP_ALLOC;
  131.     heap->size = 0;
  132.     heap->flags = 0;
  133.  
  134.     for ( i = 0 ; i < heap->length ; i++ ) {
  135.     heap->elements[i] = NULL;
  136.     }
  137.  
  138.     return heap;
  139. }
  140.  
  141.  
  142. /*****************************************************************************
  143.  * heap_build
  144.  *
  145.  * Build a heap from an unordered array.
  146.  *****************************************************************************/
  147. void heap_build( heap_t *heap )
  148. {
  149.     GLint    i;
  150.  
  151.     heap->size = heap->length;
  152.  
  153.     for ( i = PARENT( heap->length ) ; i >= 0 ; i-- ) {
  154.     heapify( heap, i );
  155.     }
  156. }
  157.  
  158.  
  159. /*****************************************************************************
  160.  * heap_extract_max
  161.  *
  162.  * Remove and return the maximum element in the heap.
  163.  *****************************************************************************/
  164. heap_elt_t *heap_extract_max( heap_t *heap )
  165. {
  166.     heap_elt_t    *max;
  167.  
  168.     if ( heap->size < 1 ) {
  169.     return NULL;
  170.     }
  171.  
  172.     max = heap->elements[0];
  173.  
  174.     heap->elements[0] = heap->elements[heap->size-1];
  175.     heap->elements[0]->index = 0;
  176.  
  177.     heap->size--;
  178.  
  179.     heapify( heap, 0 );
  180.  
  181.     return max;
  182. }
  183.  
  184.  
  185. /*****************************************************************************
  186.  * heap_insert
  187.  *
  188.  * Insert a new element into the heap.
  189.  *****************************************************************************/
  190. GLboolean heap_insert( heap_t *heap, heap_elt_t *element )
  191. {
  192.     GLint    i;
  193.  
  194.     heap->size++;
  195.  
  196.     if ( heap->size > heap->length )
  197.     {
  198.     /* Allocate some more space for the heap. */
  199.     if ( ( heap->elements =
  200.                realloc( heap->elements, ( heap->length + HEAP_ALLOC )
  201.                 * sizeof(heap_elt_t *) ) ) == NULL )
  202.     {
  203.         return GL_FALSE;
  204.     }
  205.  
  206.     heap->length += HEAP_ALLOC;
  207.     }
  208.  
  209.     i = heap->size - 1;
  210.  
  211.     while ( ( i > 0 ) &&
  212.         ( heap->elements[PARENT( i )]->value < element->value ) )
  213.     {
  214.     heap->elements[i] = heap->elements[PARENT( i )];
  215.     heap->elements[i]->index = i;
  216.  
  217.     i = PARENT( i );
  218.     }
  219.  
  220.     heap->elements[i] = element;
  221.     heap->elements[i]->index = i;
  222.  
  223.     return GL_TRUE;
  224. }
  225.  
  226.  
  227. /*****************************************************************************
  228.  * heap_delete
  229.  *
  230.  * Delete element n from the heap.
  231.  *****************************************************************************/
  232. heap_elt_t *heap_delete( heap_t *heap, GLint n )
  233. {
  234.     heap_elt_t    *element;
  235.  
  236.     if ( ( heap->size < 1 ) || ( n >= heap->size ) ) {
  237.     return NULL;
  238.     }
  239.  
  240.     element = heap->elements[n];
  241.  
  242.     heap->elements[n] = heap->elements[heap->size-1];
  243.     heap->elements[n]->index = n;
  244.  
  245.     heap->size--;
  246.  
  247.     heapify( heap, n );
  248.  
  249.     return element;
  250. }
  251.  
  252.  
  253. /*****************************************************************************
  254.  * heap_delete_ptr
  255.  *
  256.  * Delete the element with the given data pointer from the heap.
  257.  *****************************************************************************/
  258. heap_elt_t *heap_delete_ptr( heap_t *heap, void *ptr )
  259. {
  260.     heap_elt_t    *element = NULL;
  261.     GLint    i;
  262.  
  263.     if ( ( heap->size < 1 ) || ( ptr == NULL ) ) {
  264.     return NULL;
  265.     }
  266.  
  267.     for ( i = 0 ; i < heap->size ; i++ )
  268.     {
  269.     if ( heap->elements[i]->ptr == ptr ) {
  270.         element = heap->elements[i];
  271.         break;
  272.     }
  273.     }
  274.  
  275.     if ( element != NULL )
  276.     {
  277.     heap->elements[i] = heap->elements[heap->size-1];
  278.     heap->elements[i]->index = i;
  279.  
  280.     heap->size--;
  281.  
  282.     heapify( heap, i );
  283.     }
  284.  
  285.     return element;
  286. }
  287.  
  288.  
  289. /*****************************************************************************
  290.  * heap_cleanup
  291.  *
  292.  * Deallocate all memory associated with the heap.
  293.  *****************************************************************************/
  294. void heap_cleanup( heap_t **heap )
  295. {
  296.     GLint    i;
  297.  
  298.     if ( *heap )
  299.     {
  300.     if ( (*heap)->elements )
  301.     {
  302.         for ( i = 0; i < (*heap)->size; i++ )
  303.         {
  304.         if ( (*heap)->elements[i] ) {
  305.             free( (*heap)->elements[i] );
  306.         }
  307.         }
  308.         free( (*heap)->elements );
  309.     }
  310.     free( *heap );
  311.     *heap = NULL;
  312.     }
  313. }
  314.