/*
 ** 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: 2001/03/17 00:25:41 $ $Revision: 1.1 $
 ** $Header: /home/krh/git/sync/mesa-cvs-repo/Mesa/src/glu/sgi/libtess/priorityq.c,v 1.1 2001/03/17 00:25:41 brianp Exp $
 */

#include "gluos.h"
#include <stddef.h>
#include <assert.h>
#include <limits.h>		/* LONG_MAX */
#include "memalloc.h"

/* Include all the code for the regular heap-based queue here. */

#include "priorityq-heap.c"

/* Now redefine all the function names to map to their "Sort" versions. */

#include "priorityq-sort.h"

/* really __gl_pqSortNewPriorityQ */
PriorityQ *pqNewPriorityQ( int (*leq)(PQkey key1, PQkey key2) )
{
	PriorityQ *pq = (PriorityQ *)memAlloc( sizeof( PriorityQ ));
	if (pq == NULL) return NULL;

	pq->heap = __gl_pqHeapNewPriorityQ( leq );
	if (pq->heap == NULL) {
		memFree(pq);
		return NULL;
	}

	pq->keys = (PQHeapKey *)memAlloc( INIT_SIZE * sizeof(pq->keys[0]) );
	if (pq->keys == NULL) {
		__gl_pqHeapDeletePriorityQ(pq->heap);
		memFree(pq);
		return NULL;
	}

	pq->size = 0;
	pq->max = INIT_SIZE;
	pq->initialized = FALSE;
	pq->leq = leq;
	return pq;
}

/* really __gl_pqSortDeletePriorityQ */
void pqDeletePriorityQ( PriorityQ *pq )
{
	assert(pq != NULL); 
	if (pq->heap != NULL) __gl_pqHeapDeletePriorityQ( pq->heap );
	if (pq->order != NULL) memFree( pq->order );
	if (pq->keys != NULL) memFree( pq->keys );
	memFree( pq );
}


#define LT(x,y)		(! LEQ(y,x))
#define GT(x,y)		(! LEQ(x,y))
#define Swap(a,b)	if(1){PQkey *tmp = *a; *a = *b; *b = tmp;}else

/* really __gl_pqSortInit */
int pqInit( PriorityQ *pq )
{
	PQkey **p, **r, **i, **j, *piv;
	struct { PQkey **p, **r; } Stack[50], *top = Stack;
	unsigned long seed = 2016473283;

	/* Create an array of indirect pointers to the keys, so that we
	 * the handles we have returned are still valid.
	 */
	/*
  pq->order = (PQHeapKey **)memAlloc( (size_t)
                                  (pq->size * sizeof(pq->order[0])) );
	 */
	pq->order = (PQHeapKey **)memAlloc( (size_t)
			((pq->size+1) * sizeof(pq->order[0])) );
	/* the previous line is a patch to compensate for the fact that IBM */
	/* machines return a null on a malloc of zero bytes (unlike SGI),   */
	/* so we have to put in this defense to guard against a memory      */
	/* fault four lines down. from fossum@austin.ibm.com.               */
	if (pq->order == NULL) return 0;

	p = pq->order;
	r = p + pq->size - 1;
	for( piv = pq->keys, i = p; i <= r; ++piv, ++i ) {
		*i = piv;
	}

	/* Sort the indirect pointers in descending order,
	 * using randomized Quicksort
	 */
	top->p = p; top->r = r; ++top;
	while( --top >= Stack ) {
		p = top->p;
		r = top->r;
		while( r > p + 10 ) {
			seed = seed * 1539415821 + 1;
			i = p + seed % (r - p + 1);
			piv = *i;
			*i = *p;
			*p = piv;
			i = p - 1;
			j = r + 1;
			do {
				do { ++i; } while( GT( **i, *piv ));
				do { --j; } while( LT( **j, *piv ));
				Swap( i, j );
			} while( i < j );
			Swap( i, j );	/* Undo last swap */
			if( i - p < r - j ) {
				top->p = j+1; top->r = r; ++top;
				r = i-1;
			} else {
				top->p = p; top->r = i-1; ++top;
				p = j+1;
			}
		}
		/* Insertion sort small lists */
		for( i = p+1; i <= r; ++i ) {
			piv = *i;
			for( j = i; j > p && LT( **(j-1), *piv ); --j ) {
				*j = *(j-1);
			}
			*j = piv;
		}
	}
	pq->max = pq->size;
	pq->initialized = TRUE;
	__gl_pqHeapInit( pq->heap );	/* always succeeds */

#ifndef NDEBUG
	p = pq->order;
	r = p + pq->size - 1;
	for( i = p; i < r; ++i ) {
		assert( LEQ( **(i+1), **i ));
	}
#endif

	return 1;
}

/* really __gl_pqSortInsert */
/* returns LONG_MAX iff out of memory */ 
PQhandle pqInsert( PriorityQ *pq, PQkey keyNew )
{
	long curr;

	if( pq->initialized ) {
		return __gl_pqHeapInsert( pq->heap, keyNew );
	}
	curr = pq->size;
	if( ++ pq->size >= pq->max ) {
		PQkey *saveKey= pq->keys;

		/* If the heap overflows, double its size. */
		pq->max <<= 1;
		pq->keys = (PQHeapKey *)memRealloc( pq->keys, 
				(size_t)
				(pq->max * sizeof( pq->keys[0] )));
		if (pq->keys == NULL) {	
			pq->keys = saveKey;	/* restore ptr to free upon return */
			return LONG_MAX;
		}
	}
	assert(curr != LONG_MAX);	
	pq->keys[curr] = keyNew;

	/* Negative handles index the sorted array. */
	return -(curr+1);
}

/* really __gl_pqSortExtractMin */
PQkey pqExtractMin( PriorityQ *pq )
{
	PQkey sortMin, heapMin;

	if( pq->size == 0 ) {
		return __gl_pqHeapExtractMin( pq->heap );
	}
	sortMin = *(pq->order[pq->size-1]);
	if( ! __gl_pqHeapIsEmpty( pq->heap )) {
		heapMin = __gl_pqHeapMinimum( pq->heap );
		if( LEQ( heapMin, sortMin )) {
			return __gl_pqHeapExtractMin( pq->heap );
		}
	}
	do {
		-- pq->size;
	} while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL );
	return sortMin;
}

/* really __gl_pqSortMinimum */
PQkey pqMinimum( PriorityQ *pq )
{
	PQkey sortMin, heapMin;

	if( pq->size == 0 ) {
		return __gl_pqHeapMinimum( pq->heap );
	}
	sortMin = *(pq->order[pq->size-1]);
	if( ! __gl_pqHeapIsEmpty( pq->heap )) {
		heapMin = __gl_pqHeapMinimum( pq->heap );
		if( LEQ( heapMin, sortMin )) {
			return heapMin;
		}
	}
	return sortMin;
}

/* really __gl_pqSortIsEmpty */
int pqIsEmpty( PriorityQ *pq )
{
	return (pq->size == 0) && __gl_pqHeapIsEmpty( pq->heap );
}

/* really __gl_pqSortDelete */
void pqDelete( PriorityQ *pq, PQhandle curr )
{
	if( curr >= 0 ) {
		__gl_pqHeapDelete( pq->heap, curr );
		return;
	}
	curr = -(curr+1);
	assert( curr < pq->max && pq->keys[curr] != NULL );

	pq->keys[curr] = NULL;
	while( pq->size > 0 && *(pq->order[pq->size-1]) == NULL ) {
		-- pq->size;
	}
}