diff options
Diffstat (limited to 'libtess/priorityq.h')
| -rw-r--r-- | libtess/priorityq.h | 124 |
1 files changed, 0 insertions, 124 deletions
diff --git a/libtess/priorityq.h b/libtess/priorityq.h deleted file mode 100644 index 750bdc8..0000000 --- a/libtess/priorityq.h +++ /dev/null @@ -1,124 +0,0 @@ -/* -** License Applicability. Except to the extent portions of this file are -** made subject to an alternative license as permitted in the SGI Free -** Software License B, Version 1.1 (the "License"), the contents of this -** file are subject only to the provisions of the License. You may not use -** this file except in compliance with the License. You may obtain a copy -** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 -** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: -** -** http://oss.sgi.com/projects/FreeB -** -** Note that, as provided in the License, the Software is distributed on an -** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS -** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND -** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A -** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. -** -** Original Code. The Original Code is: OpenGL Sample Implementation, -** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, -** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. -** Copyright in any portions created by third parties is as indicated -** elsewhere herein. All Rights Reserved. -** -** Additional Notice Provisions: The application programming interfaces -** established by SGI in conjunction with the Original Code are The -** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released -** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version -** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X -** Window System(R) (Version 1.3), released October 19, 1998. This software -** was created using the OpenGL(R) version 1.2.1 Sample Implementation -** published by SGI, but has not been independently verified as being -** compliant with the OpenGL(R) version 1.2.1 Specification. -** -*/ -/* -** Author: Eric Veach, July 1994. -** -** $Date$ $Revision$ -** $Header$ -*/ - -#ifndef __priorityq_sort_h_ -#define __priorityq_sort_h_ - -#include "priorityq-heap.h" - -#undef PQkey -#undef PQhandle -#undef PriorityQ -#undef pqNewPriorityQ -#undef pqDeletePriorityQ -#undef pqInit -#undef pqInsert -#undef pqMinimum -#undef pqExtractMin -#undef pqDelete -#undef pqIsEmpty - -/* Use #define's so that another heap implementation can use this one */ - -#define PQkey PQSortKey -#define PQhandle PQSortHandle -#define PriorityQ PriorityQSort - -#define pqNewPriorityQ(leq) __gl_pqSortNewPriorityQ(leq) -#define pqDeletePriorityQ(pq) __gl_pqSortDeletePriorityQ(pq) - -/* The basic operations are insertion of a new key (pqInsert), - * and examination/extraction of a key whose value is minimum - * (pqMinimum/pqExtractMin). Deletion is also allowed (pqDelete); - * for this purpose pqInsert returns a "handle" which is supplied - * as the argument. - * - * An initial heap may be created efficiently by calling pqInsert - * repeatedly, then calling pqInit. In any case pqInit must be called - * before any operations other than pqInsert are used. - * - * If the heap is empty, pqMinimum/pqExtractMin will return a NULL key. - * This may also be tested with pqIsEmpty. - */ -#define pqInit(pq) __gl_pqSortInit(pq) -#define pqInsert(pq,key) __gl_pqSortInsert(pq,key) -#define pqMinimum(pq) __gl_pqSortMinimum(pq) -#define pqExtractMin(pq) __gl_pqSortExtractMin(pq) -#define pqDelete(pq,handle) __gl_pqSortDelete(pq,handle) -#define pqIsEmpty(pq) __gl_pqSortIsEmpty(pq) - - -/* Since we support deletion the data structure is a little more - * complicated than an ordinary heap. "nodes" is the heap itself; - * active nodes are stored in the range 1..pq->size. When the - * heap exceeds its allocated size (pq->max), its size doubles. - * The children of node i are nodes 2i and 2i+1. - * - * Each node stores an index into an array "handles". Each handle - * stores a key, plus a pointer back to the node which currently - * represents that key (ie. nodes[handles[i].node].handle == i). - */ - -typedef PQHeapKey PQkey; -typedef PQHeapHandle PQhandle; -typedef struct PriorityQ PriorityQ; - -struct PriorityQ { - PriorityQHeap *heap; - PQkey *keys; - PQkey **order; - PQhandle size, max; - int initialized; - int (*leq)(PQkey key1, PQkey key2); -}; - -PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) ); -void pqDeletePriorityQ( PriorityQ *pq ); - -int pqInit( PriorityQ *pq ); -PQhandle pqInsert( PriorityQ *pq, PQkey key ); -PQkey pqExtractMin( PriorityQ *pq ); -void pqDelete( PriorityQ *pq, PQhandle handle ); - -PQkey pqMinimum( PriorityQ *pq ); -int pqIsEmpty( PriorityQ *pq ); - -#endif |